Princípio da Indução Finita

O Princípio da Indução Finita (ou Princípio da Indução, também conhecido como PIF) é uma maneira de provarmos que uma afirmação sobre um número natural $n$ é válida para todo número natural $n \geq n_0$ para algum $n_{0}$.

Como provar que alguma propriedade vale para todo número natural?

Existem coisas que você quer provar que valem para todo número natural. Por exemplo,

$1+2+\cdots +n={\frac {n(n+1)}{2}}.$

Você pode até pensar: vamos verificar que a igualdade é válida para alguns valores: $n=1,2,3$ etc. Se você fizer isso, perceberá que funciona: a igualdade é válida para estes números. Mas afinal, ela vale para todo $n$ natural? Ora, verificar algo para vários valores não é uma prova? NÃO. Veja os seguintes exemplos:

Exemplo

É verdade que a expressão $n^{4}-10x^{3}+35x^{2}-50x+24$ é igual a zero para todo n natural?

Solução:

Vejamos esta expressão para alguns valores de $n$:

• $n=1$

$1^{4}-10.1^{3}+35.1^{2}-50.1+24=1-10+35-50+24=0.$

• $n=2$

$2^{4}-10.2^{3}+35.2^{2}-50.2+24=16-80+140-100+24=0.$

• $n = 3$

$3^{4}-10.3^{3}+35.3^{2}-50.3+24=81-270+315-150+24=0.$

• $n = 4$

$4^{4}-10.4^{3}+35.4^{2}-50.4+24=256-640+560-200+24=0.$

A afirmação é verdadeira para $n=1,2,3$ e $4$. Podemos dizer que ela vale sempre? NÃO. Ela não vale para $n=5$:

$5^{4}-10.5^{3}+35.5^{2}-50.5+24=625-1250+825-250+24=-26.$

Exemplo

Para todo $n$ natural, $f(n)=n^{2}-n+41$ é um número primo? Se você fizer $n=0,1,2,3,\cdots ,40$ irá obter somente números primos. Mas $f(41)=41^{2}-41+41=41^{2}$que não é um número primo. (Este é o chamado Polinômio de Euler).

Também, a expressão $f(n)=n^{2}-n+41$ resulta em número primo para $n=0,1,2,\cdots ,39$ nos dá números primos, mas $n=40$ não.

A expressão $f(n)=8n^{2}-488n+7243$ resulta em um número primo para $n=0,1,2,\cdots ,61$, mas não é um número primo para $n=62$.

Exemplo

Se $d(n)$ é a quantidade de divisores positivos de $n$, a expressão $\operatorname {mdc} (d(k^{3}),d(k))$ é uma potência de $2$, ou seja, um número da forma $2^{w}$, para $k=1,2,3,\cdots ,431$, mas ela não é dessa forma para $k=432$.

Exemplo

Existe um número matemática famoso dentro da matemática chamado de número de Euler que é um número, representado por $e$, que vale aproximadamente $2,7182818284\cdots$. Ele tem infinitas casas decimais. O número

$\left(1+9^{-4^{6\times 7}}\right)^{3^{2^{85}}}$

possui os $18457734525360901453873570$ primeiros algarismos iguais aos de $e$. Mas ele não é igual a $e$.

Exemplo

Dá para dizer que todo número da forma $999n^{2}+1$ não é quadrado perfeito, para todo $n \geq 1$ natural? Se você testar $n=1,2,3,\cdots$, vai descobrir que nenhum desses é quadrado perfeito. Aliás você pode testar até $12055735790331359447442538766$ (aproximadamente 12 octilhões) e ver que vale. Mas para o próximo número já não valerá mais.

Princípio da Indução Finita

Seja $P(n)$ uma propriedade do número natural $n$. O Princípio da Indução Finita (ou Princípio da Indução ou Princípio da Indução Matemática) estabelece que: se as afirmações a seguir são verdadeiras,

(i) (Base da Indução) $P(1)$ é verdadeira;

(ii) (Passo Indutivo) Para todo $n$ natural, vale que "se $P(n)$ é verdadeira então $P(n+1)$ também é verdadeira".

então $P(n)$ é verdadeira para qualquer $n \geq 1$ natural.

Quando estivermos provando que "se $P(n)$ então $P(n+1)$" no item (ii), a afirmação $P(n)$ é chamada de hipótese de indução.

Como Usar a Indução?

Existem duas maneiras comuns em textos de indução. Vamos mostrar aqui as duas, para que você possa ler tranquilamente em outros textos quando uma ou outra aparecer.

1ª Maneira:

• (Base da Indução) Mostre que a afirmação é verdadeira para $n=1$.
• (Passo Indutivo) Suponha que a afirmação seja válida para $n=k$ e use o que você obteve (que é chamado de hipótese de indução) para mostrar que ela também é válida para $n=k+1$.

2ª Maneira:

• (Base da Indução) Mostre que a afirmação é verdadeira para $n=1$.
• (Passo Indutivo) Suponha que a afirmação seja válida para $n$ e use o que você obteve (que é chamado de hipótese de indução) para mostrar que ela também é válida para $n+1$.

Observe que as duas maneiras são quase iguais. Mas como elas podem aparecer nos textos, deixamos aqui para que você se acostume como elas.

Veja que, se a afirmação for válida para $n=1$, e para $n=k+1$ caso seja para $n=k$, de fato será válida para todo número natural: se $n=k=1$ (caso em que já provamos a validade), então também será para $n=k+1=2$. Assim, por este processo, concluímos que a afirmação é válida para $n = 3$, $n = 4$, e assim por diante.

Observação

Uma boa maneira de pensar no passo indutivo é ver se você consegue relacionar a afirmação para $n=k+1$ com ela para $n=k$.

Observação

Se o enunciado lhe pedir para encontrar algo para um valor muito grande de $n$, uma possível estratégia é verificar que aquilo é válido para todo $n$ natural (usando indução) e depois particularizar para o valor do enunciado.

Exemplo

Prove que para todo $n \geq 1$ inteiro vale a igualdade

$1+2+\cdots +n={\frac {n(n+1)}{2}}.$

Solução 1: Vamos começar mostrando que a igualdade é válida para $n=1$. Observe que neste caso, a igualdade do enunciado se torna

$1={\frac {1(1+1)}{2}},$

que é verdade. Logo, o caso $n=1$ é verdadeiro.

Suponha agora que a igualdade seja válida para $n=k$, ou seja,

$1+2+\cdots +k={\frac {k(k+1)}{2}}.$

Esta é a nossa hipótese de indução. Vamos usá-la para mostrar que a igualdade é válida para $n=k+1$, isto é,

$1+2+\cdots +k+(k+1)={\frac {(k+1)(k+2)}{2}}.$

Para isto, vamos partir do lado esquerdo da igualdade e chegar na do lado direito. E como usar a hipotése de indução aqui? Repare que na expressão do lado direito aparece $1+2+\cdots +k$. Podemos trocá-la por ${\frac {k(k+1)}{2}}$. Desta forma, se fizermos isto e colocarmos $k+1$ em evidência,

$1+2+\cdots +k+(k+1)={\frac {k(k+1)}{2}}+(k+1)=(k+1)\left({\frac {k}{2}}+1\right)={\frac {(k+1)(k+2)}{2}}.$

Desta forma, a igualdade do enunciado é verdadeira para todo $n \geq 1$.

Solução 2: O caso $n=1$ é exatamente igual ao da solução anterior. Vamos supor que a afirmação seja válida para $n$, isto é,

$1+2+\cdots +n={\frac {n(n+1)}{2}}.$

Esta é a nossa hipótese de indução. Vamos usá-la para mostrar que a igualdade é válida para $n+1$, isto é,

$1+2+\cdots +n+(n+1)={\frac {(n+1)(n+2)}{2}}.$

Para isto, vamos partir do lado esquerdo da igualdade e chegar na do lado direito. E como usar a hipotése de indução aqui? Repare que na expressão do lado direito aparece $1+2+\cdots +n$. Podemos trocá-la por $\frac{n(n+1)}{2}$. Desta forma, se fizermos isto e colocarmos $n+1$ em evidência,

$1+2+\cdots +n+(n+1)={\frac {n(n+1)}{2}}+(n+1)=(n+1)\left({\frac {n}{2}}+1\right)={\frac {(n+1)(n+2)}{2}}.$

Desta forma, a igualdade do enunciado é verdadeira para todo $n \geq 1$.

Exemplo

Demonstre que a soma dos $n$ primeiros números ímpares é igual a $n^2$.

Solução: Resolveremos por indução matemática. Inicialmente, note que o n-ésimo número ímpar é igual a $2n-1$. Logo, a soma dos $n$ primeros números ímpares é $1+3+5+\cdots +(2n-1)$. Para $n=1$, temos que a soma é $1=1^2$, então a afirmação é válida. Supondo ser válido para $n=k$, segue que $1+3+5+\cdots +(2k-1)=k^{2}$. E, para $n=k+1$, a soma dos $n+1$ primeiros números ímpares é $1+3+5+\cdots +(2k-1)+(2k+1)$; como $1+3+5+\cdots +(2k-1)=k^{2}$, a soma dos $k+1$ primeiros números ímpares é $k^2+2k+1=(k+1)^2$. Assim, de fato, a soma dos $n$ primeiros números ímpares é igual a $n^2$.

Exemplo (OBMEP 2013 - 2ª Fase - Nível 3)

Hipácia criou duas novas operações com números naturais, indicadas por $\triangle$ e $\square$, com as seguintes propriedades:

• $a \triangle b = (a+b)+1$
• $a \square b = b \square a$
• $0 \square 0 = 1$
• $a \square (b \triangle c) = (a \square b) \triangle (a \square c)$

Por exemplo $0 \triangle 0 = (0+0)+1 = 1$. Observe na ilustração como Hipácia calculou $0 \square 1$.

a) Calcule $2 \triangle 3$.

Usando a regra do enunciado, $2 \triangle 3 = 2+3+1 = 6$.

b) Calcule $0 \square 3$.

Não temos uma fórmula explícita para $\square$, então vamos desenvolver uma. Temos que $0 \square 0 = 1$, $0\square 1=3$. Vamos provar por indução que $0\square n=2n+1$. Já temos os casos base, agora suponha que $0\square k=2k+1$ para algum $k$. Temos que:

$0\square (0\triangle k)=(0\square 0)\triangle (0\square k)\implies 0\square (k+1)=(0\square k)+2=2k+1+2=2(k+1)+2$

Ou seja, se vale para $k$, também vale para $k+1$. Provamos o passo indutivo! Dessa forma, $0\square 3=2\cdot 3+1=7$.

c) Calcule $2 \square 3$.

Vamos analisar agora o que acontece com $a\square b$:

$a\square b=a\square ((b-1)\triangle 0)=(a\square (b-1))\triangle (a\square 0)=(a\square (b-1))\triangle (2a+1)$

Ou seja, parece que conseguimos determinar $a\square b$ com base em $a\square (b-1)$. Observe que:

$a\square 0=2a+1$

$a\square 1=(a\square 0)\triangle (a\square 0)=2a+1+2a+1+1=4a+3$

$a\square 2=(a\square 0)\triangle (a\square 1)=2a+1+4a+3+1=6a+5$

$a\square 3=(a\square 0)\triangle (a\square 2)=2a+1+6a+5+1=8a+7$

Parece razoável querer provar que $a\square b=(2b+2)a+(2b+1)=2ab+2a+2b+1$. Pegamos um $a$ qualquer, com os casos base descritos acima, e supomos que $a\square b=2ab+2a+2b+1$ para algum $b$, então:

$a\square (b+1)=(a\square 0)\triangle (a\square b)=2a+1+2ab+2a+2b+1+1=2a(b+1)+2a+2(b+1)+1$

O que prova que também vale para $b+1$, completando o passo indutivo. Assim, temos que $a\square b=2ab+2a+2b+1$ para todos os $a, b$, o que significa que $2\square 3=2\cdot 2\cdot 3+2\cdot 2+2\cdot 3+1=12+4+6+1=23$.

Exemplo (OBM 2003 - 3ª Fase - Nível 2)

Há $N$ cidades na Tumbólia. Cada duas cidades desse país são ligadas por uma rodovia ou uma ferrovia, não existindo nenhum par de cidades ligadas por ambos os meios. Um turista deseja viajar por toda a Tumbólia, visitando cada cidade exatamente uma vez, e retornar a cidade onde ele começou sua jornada. Prove que é possível escolher a ordem na qual as cidades serão visitadas de modo que o turista mude o meio de transporte no máximo uma vez.

Solução: O caso $N = 2$ é trivial. Para o caso $N=3$, basta apenas escolher para começar uma cidade que está ligada às duas outras por meios de transporte diferentes. Vamos supor, agora, que funciona para $N=k$ cidades e provar que funciona para $N=k+1$.

Separe uma das cidades, e chame-a de $X$. É possível escolher uma sequência de cidades entre as $k$ restantes que permita que o turista visite-as mudando de meio de transporte no máximo uma vez. Nessa sequência, vamos chamar a cidade que começa e encerra o ciclo de $A$, a primeira cidade visitada após $A$ de $B$, e a última cidade visitada antes de voltar a $A$ de $C$. Vamos separar em alguns casos.

Caso 1: Se $A \leftrightarrow B$ e $C\leftrightarrow A$ forem feitos pelo mesmo meio de transporte, significa que não trocamos de meio de transporte na viagem; mesmo assim, ainda é possível concluir o problema, separando em dois casos: Se $X$ se ligar a todos pelo mesmo meio de transporte, é trivial. Mas se há pelo menos uma conexão diferente, escolhemos uma cidade $D\neq X$ tal que $X\leftrightarrow D$ seja feito por um meio de transporte diferente, de onde podemos começar em $D$, passar por todas as cidades menos $X$, passar por $X$ e voltar a $D$ trocando de transporte uma única vez.

Caso 2: Se $A \leftrightarrow B$ e $C\leftrightarrow A$ forem feitos por meios de transporte diferentes, trocamos de meio exatamente uma vez (pela hipótese de indução), então precisamos verificar mais casos. Vamos representar as sentenças "$P\leftrightarrow Q$ é uma rodovia" e "$P\leftrightarrow Q$ é uma ferrovia" como $P-Q$ e $P = Q$. Vamos supor, sem perdas, que $A-B$ e $C=A$.

Caso 2a: $X-A$ e $X-B$.

Podemos fazer $A-X-B-\dots =C=A$.

Caso 2b: $X = A$ e $X-B$.

Podemos fazer $X-B-\dots =C=A=X$.

Caso 2c: $X = A$ e $X=B$.

Podemos fazer $A=X=C=\dots -B-A$.

Caso 2d: $X-A$ e $X=B$.

Subcaso 1: $X=C$.

Podemos fazer $X-A-B-\dots =C=X$.

Subcaso 2: $X-C$.

Podemos fazer $C-X-A-B-\dots =C$.

Como cobrimos todos os casos, $N=k+1$ sempre funciona e o problema acabou.

Exemplo (OBM 2020 - Nível 3)

Prove que existem inteiros positivos $a_{1},a_{2},\ldots ,a_{2020}$ tais que:

${\dfrac {1}{a_{1}}}+{\dfrac {1}{2a_{2}}}+{\dfrac {1}{3a_{3}}}+\ldots +{\dfrac {1}{2020a_{2020}}}=1$.

Solução: O número 2020 não parece ser "específico" para esse fato, melhor dizendo, não há uma propriedade do 2020 que o torne o único número para o qual essa propriedade funciona. De fato, pretendemos provar que, para todo $n$ inteiro positivo, existem inteiros positivos $a_1, a_2, \ldots, a_n$tais que

$\sum _{k=1}^{n}{\dfrac {1}{ka_{k}}}={\dfrac {1}{a_{1}}}+{\dfrac {1}{2a_{2}}}+\ldots +{\dfrac {1}{na_{n}}}=1$

Para isso, é bom fazer alguns casos-base. O caso $n=1$é óbvio: $a_1=1$. O caso $n=2$ funciona com $a_{1}=a_{2}=3$.

Se supormos que a propriedade é válida para $n$, vamos provar que ela vale para $n+1$:

${\dfrac {1}{a_{1}}}+{\dfrac {1}{2a_{2}}}+\ldots +{\dfrac {1}{na_{n}}}=1$

Para isso, uma ideia é decompor ${\dfrac {1}{na_{n}}}$em duas frações cujos denominadores sejam múltiplos de $n$ e $n+1$, para provar que o $n+1$-ésimo inteiro existe. Como queremos um denominador produto de $n+1$, podemos multiplicar ${\dfrac {1}{na_{n}}}$ por ${\dfrac {n+1}{n+1}}$ para obter:

${\dfrac {n+1}{n(n+1)a_{n}}}={\dfrac {\cancel {n}}{{\cancel {n}}(n+1)a_{n}}}+{\dfrac {1}{n(n+1)a_{n}}}={\dfrac {1}{(n+1)a_{n}}}+{\dfrac {1}{n(n+1)a_{n}}}$

Assim sendo:

${\dfrac {1}{a_{1}}}+{\dfrac {1}{2a_{2}}}+\ldots +{\dfrac {1}{n(n+1)a_{n}}}+{\dfrac {1}{(n+1)a_{n}}}=1$

Assim, os $n+1$ inteiros existem, são eles: $a_{1},a_{2},\ldots a_{n-1},(n+1)a_{n},a_{n}$. Pelo Princípio da Indução Finita, esses inteiros existem para qualquer $n$, assim, também existem para $n=2020$, e a prova acabou.

Exemplo (Desigualdade de Bernoulli)

Prove que $(1+r)^{n}\geq 1+r\cdot n$ para todo $r > 0$.

Solução: Por indução matemática, começamos por $n=1$, para o qual temos que $(1+r)^{1}=1+r\cdot 1\geq 1+r\cdot 1$ (o que, de fato, está certo). Supondo ser verdadeiro para $n=k$, temos que $(1+r)^{k}\geq 1+rk$. Para $n=k+1$, segue que $(1+r)^{k+1}=(1+r)^{k}\cdot (1+r)\geq (1+rk)(1+r)=1+r+rk+r^{2}k=1+r(k+1)+r^{2}k>1+r(k+1)$, logo $(1+r)^{k+1}\geq 1+r(k+1)$. Portanto, é válido que $(1+r)^{n}\geq 1+r\cdot n$ para todo $r > 0$.

Exemplo

Seja $n$ um inteiro positivo. Para cada um dos inteiros $n+1,n+2,\cdots ,2n$ considere o seu maior divisor ímpar. Prove que a soma de todos estes divisores é igual a $n^2$.

Solução: Inicialmente, vamos definir uma função $f$ tal que $f(n)$ seja o maior divisor ímpar de $n$. Para $n=1$, temos a soma $S_{1}=f(2)=1$ (veja que o maior divisor ímpar de $2$ é $1$). Supondo que a propriedade seja válida para $n=k$, temos que $f(k+1)+f(k+2)+\cdots +f(2k)=k^{2}$. Para $n=k+1$, temos $S_{k+1}=f(k+2)+f(k+3)+\cdots +f(2k)+f(2k+1)+f(2k+2)$; note que $2k+2=2(k+1)$, logo $f(2k+2)=f(k+1)$ (pois qualquer divisor ímpar de $2k+2$ está entre os divisores ímpares de $k+1$). E, como $2k+1$ é ímpar, $f(2k+1)=2k+1$. Assim, segue que $S_{k+1}=f(k+2)+f(k+3)+\cdots +f(2k)+[2k+1]+f(k+1)=k^{2}+2k+1=(k+1)^{2}$. Está, portanto, provado que a soma de todos os referidos divisores é igual a $n^2$.

Exemplo (Cone Sul 1992)

Considere o conjunto $S$ de $100$ números: $1,{\frac {1}{2}},{\frac {1}{3}},...,{\frac {1}{100}}$. Quaisquer dois números, $a$ e $b$, são eliminados em $S$, e o número $a+b+ab$ é adicionado. Agora, existem $99$ números em $S$. Depois de fazermos esta operação $99$ vezes, existe apenas $1$ número em $S$. Quais valores este número pode ter?

Dica:

Defina $*$ de forma que $a*b=a+b+ab$. Prove que $a*b = b*a$ e que $a * (b * c) = (a * b) * c$. Em seguida, prove por indução em $n$ que $1*{\frac {1}{2}}*{\frac {1}{3}}*...*{\frac {1}{n}}=n$

Solução: Vamos começar com casos particulares para entendermos melhor o problema.Para nos ajudar, vamos considerar a operação $*$ definida por $x*y=x+y+xy$. Essa operação tem algo interessante: $x*y=y*x$, para quaisquer $x$ e $y$ reais (o que chamamos de propriedade comutativa da operação).

Se começarmos com $2$ núumeros, digamos $a$ e $b$, terminaremos com o número $a*b$.

Já se começarmos com $a$, $b$ e $c$, existem três possibilidades para o número final: $(a*b)*c$, $(b*c)*a$ e $(c*a)*b$. Aqui acontece uma coisa interessante: os três números são iguais. Coincidência? Não! De fato, para quaisquer $x$,$y$ e $z$ reais vale o seguinte: $(x*y)*z=x*(y*z)$ (isto é o que chamamos de propriedade associativa). Desta forma, se começarmos com $a$, $b$ e $c$, terminaremos com $a*b*c$.

E se os números do começo forem $a$, $b$, $c$ e $d$? Se combinarmos as propriedades comutativa e associativa, veremos que a única possibilidade para o último número será $a*b*c*d$. O mesmo vale para qualquer quantidade de termos iniciais.

Desta forma, o número final do problema será

$1*{\frac {1}{2}}*{\frac {1}{3}}*...*{\frac {1}{100}}.$

Com isso, para terminarmos o problema precisamos calcular este valor. Façamos alguns casos particulares.

• $n=1$

$1=1$

• $n=2$

$1*{\frac {1}{2}}=1+{\frac {1}{2}}+1.{\frac {1}{2}}=2$

• $n = 3$

$1*{\frac {1}{2}}*{\frac {1}{3}}=(1*{\frac {1}{2}})*{\frac {1}{3}}=2*{\frac {1}{3}}=2+{\frac {1}{3}}+2.{\frac {1}{3}}=3.$

Podemos suspeitar que

$1*{\frac {1}{2}}*{\frac {1}{3}}*...*{\frac {1}{n}}=n.$

Será? Lembre-se: fazer alguns exemplos não prova nada! Vamos usar indução em $n$ para provar este resultado. Já provamos que esta afirmação vale para $n=1$. Suponha que ela seja válida para $n=k$, ou seja,

$1*{\frac {1}{2}}*{\frac {1}{3}}*...*{\frac {1}{k}}=k.$

Provaremos que ela vale para $n=k+1$. Com efeito, $1*{\frac {1}{2}}*{\frac {1}{3}}*...*{\frac {1}{k}}*{\frac {1}{k+1}}=k*{\frac {1}{k+1}}=k+{\frac {1}{k+1}}+{\frac {k}{k+1}}=k+1.$

Logo,

$1*{\frac {1}{2}}*{\frac {1}{3}}*...*{\frac {1}{n}}=n.$

Em particular,

$1*{\frac {1}{2}}*{\frac {1}{3}}*...*{\frac {1}{100}}=100.$

Ou seja, irá sobrar somente o número $100$.

Exemplo (Cone Sul 2001)

Em cada casa de um tabuleiro quadriculado $2000\times 2000$ deve-se escrever um dos três numeros: $-1,0$ ou $1$. Se, em seguida, somam-se os números escritos em cada linha e cada coluna, obtêm-se $4000$ resultados. Mostre que é possível preencher o tabuleiro de modo que os $4000$ resultados assim obtidos sejam todos distintos.

Solução: Comecemos com pequenos casos: uma tabela $2 \times 2$.

A partir daí, vamos aproveitar este tabuleiro para preenchermos um que seja $4 \times 4$.

Vamos manter iguais as somas da primeira e da segunda linhas e da primeira e segunda colunas. Como fazer isto? Basta colocarmos $1$ e $-1$ em cada uma das fileiras.

Já temos as somas $-1, 0, 1, 2$. Façamos aparecer $-3,-2,3,4$.

Podemos fazer isto de maneira mais geral: construiremos um tabuleiro $(2k+2)\times (2k+2)$, que satisfaça as condições do enunciado, a partir de um tabuleiro $2k\times 2k$.

Suponhamos que o tabuleiro $2k\times 2k$ tenha somas de suas fileiras iguais a $-(2k-1),-(2k-2),\dots ,2k-2,2k-1,2k$. Coloque o tabuleiro $2k\times 2k$ no canto esquerdo superior.

Para que as somas das primeiras $2k$ e $2k$ colunas não mudem, colocaremos $1$ e $-1$ para que as somas se cancelem. Mais precisamente, nas $2k$ primeiras casas da $2k+1$-ésima linha e da $2k+1$-ésima coluna, colocaremos $1$'s. Já as $2k$ primeiras casas da $2k+2$-ésima linha e da $2k+2$-ésima coluna, colocaremos $-1$'s.

Nas fileiras que ainda não calculamos as somas, façamos aparecer $-(2k+1),-2k,2k+1,2k+2$. Para isto, façamos conforme a figura abaixo.

Assim, conseguimos todas as somas distintas (que irão variar de $-(2k+1)$ a $2k+2$). Portanto é possível preencher um tabuleiro $2n \times 2n$ conforme as condições do enunciado para todo $n$. Em particular, podemos fazer isso para o tabuleiro $2000\times 2000$.

Exemplo (OBM 2006 - 3ª Fase - Nível 2)

Em um torneio de tênis de mesa (no qual nenhum jogo termina empatado), cada um dos $n$ participantes jogou uma única vez contra cada um dos outros. Sabe-se que, para todo $k>2$, não existem $k$ jogadores $J_{1},J_{2},\dots ,J_{k}$ tais que $J_1$ ganhou de $J_2$, $J_2$ ganhou de $J_3$, $J_3$ ganhou de $J_{4}$, ..., $J_{k-1}$ ganhou de $J_k$, $J_k$ ganhou de $J_1$.

Prove que existe um jogador que ganhou de todos os outros e existe um jogador que perdeu de todos os outros.

Solução: Vamos usar indução em $n$. Para ajudar a nossa escrita, escrevermos $Y\rightarrow X$ para indicar que $X$ ganhou de $Y$.

• $n = 3$

Sejam $A$, $B$ e $C$ os três jogadores. Podemos supor sem perda de generalidade que $B \rightarrow A$. Analisemos as possibilidades para os resultados do jogo de $B$ contra $C$.

1º Caso: $C \rightarrow B$

Quanto o fica o jogo entre $A$ e $C$ neste caso? Observe que não podemos ter $A\rightarrow C$, pois aí não teríamos as condições do enunciado. Logo $C\rightarrow A$. Aqui, $A$ é o jogador que ganhou de todos e $C$ o perdedor das duas partidas que jogou.

2º Caso: $B\rightarrow C$

Neste caso, $B$ é o perdedor. Já para encontrarmos o vencedor, basta tomarmos aquele que vencer a partida entre $A$ e $C$.

Portanto, a afirmação vale para o caso $n = 3$.

• Suponhamos que a afirmação do enunciado seja válida para $n$ jogadores e provemos que ela vale para $n+1$.

Vamos nomear os jogadores aqui também: $A_{1},A_{2},\dots ,A_{n},A_{n+1}$. Para podermos usar a hipótese de indução, consideremos apenas os jogos entre $A_1,A_2,\dots,A_n$. Se usarmos-a, poderemos concluir que existe um jogador que vence todas essas partidas, que chamaremos, sem perda de generalidade, de $A_1$.

Ao acrescentarmos o jogador $A_{n+1}$ que será o vencedor: $A_1$ ou $A_{n+1}$. Para descobrirmos isso, precisamos analisar os possíveis resultados do jogo entre os dois.

1º Caso: $A_{n+1}\rightarrow A_{1}$

Neste caso, $A_1$ é o jogador que venceu todas as partidas.

2º Caso: $A_{1}\rightarrow A_{n+1}$

Nenhum dos jogadores $A_{2},\dots ,A_{n}$ pode ser o ganhador, pois todos estes perderam de $A_1$. Será que $A_{n+1}$ ganhou de todos esses? Observe que não podemos ter $A_{n+1}\rightarrow A_{2}$, pois isto implicaria $A_{1}\rightarrow A_{n+1}$, $A_{n+1}\rightarrow A_{2}$ e $A_{2}\rightarrow A_{1}$, o que contradiz o enunciado. Logo, $A_{2}\rightarrow A_{n+1}$. Analogamente, $A_{3},\dots ,A_{n}$ perderam de $A_{n+1}$, o que torna este o vencedor.

Portanto, sempre existe um vencedor neste campeonato.

Exemplo (OBM 2007 - 3ª Fase - Nível 3)

Seja $f(x)=x^{2}+2007x+1$. Prove que, para todo $n$ inteiro positivo, a equação $\underbrace{f(f(\cdots (f}_{n \text{ vezes}}(x))\cdots ))$ tem pelo menos uma solução real.

Solução: Parece muito chato ficar escrevendo toda hora

$\underbrace{f(f(\cdots (f}_{n \text{ vezes}}(x))\cdots ))$.

Por isso, vamos colocar uma notação melhor: chamaremos esta expressão de $f^n(x)$. Assim $f^1(x)=f(x)$ e $f^{n+1}(x)=f^n(f(x))$ para $n \geq 1$.

O enunciado nos pede para mostrar que para todo $n$ inteiro positivo, existe $x_n$ real tal que $f^{n}(x_{n})=0$. Vamos montar uma estratégia. Já que queremos provar que algo vale para $n$ inteiro positivo, parece interessante usar indução em $n$. Para isto, vamos procurar uma relação entre $x_{n+1}$ e $x_n$ (para usarmos no passo indutivo).

Como iremos provar na base da indução que existe $x_1$ tal que $f(x_{1})=0$, é suficiente forçarmos no passo indutivo que $f^{n+1}(x_{n+1})=f^{n}(x_{n})$ para $n \geq 1$. Como esta igualdade equivale a $f^{n}(f(x_{n+1}))=f^{n}(x_{n})$, é suficiente forçarmos $f(x_{n+1})=x_{n}(*)$ para $n \geq 1$.

Mas quem irá garantir que $x_n$ será um número real? Observe que a igualdade $(*)$ é equivalente a

$x_{n+1}^{2}+2007x_{n+1}+1=x_{n}\Leftrightarrow x_{n+1}^{2}+2007x_{n+1}+1-x_{n}=0.$

Note que uma das raízes desta equação é

$x_{n+1}={\frac {-2007+{\sqrt {\Delta _{n+1}}}}{2}}$

com $\Delta _{n+1}=2007^{2}-4+4x_{n}$.

Agora sim nós já exploramos o problema, vamos executar um plano: construir $\Delta_n$ por indução de forma que seja formada por termos positivos e a partir desta sequência, construimos $(x_n)$. Considere $\Delta _{1}=2007^{2}-4$ e $x_{1}={\frac {-2007+{\sqrt {\Delta _{1}}}}{2}}$. Vamos mostrar por indução em $n$ que existe uma sequência $(\Delta _{n})$ de números reais de forma que se definirmos $x_{n}={\frac {-2007+{\sqrt {\Delta _{n}}}}{2}}(**)$ teremos $f^{n}(x_{n})=0$ e $\Delta_n$ é positivo para todo $n$ natural.

Comecemos com o caso $n=1$. Observe que, pela forma que definimos, $\Delta _{1}>0$. Além disso, $f(x_{1})=0$ (basta vermos que $x_1$ é uma das raízes de $x^{2}+2007x+1=0$).

Vamos supor que a afirmação seja válida para $n$, ou seja $\Delta _{n}>0$ e $f^{n}(x_{n})=0$, e mostrar que ela também vale para o caso $n+1$. Para isto, vamos considerar $\Delta _{n+1}=2007^{2}-4+4x_{n}$. Observe que

$\Delta _{n+1}=2007^{2}-4+4\left({\frac {-2007+{\sqrt {\Delta _{n}}}}{2}}\right)=2007^{2}-4018+{\sqrt {\Delta _{n}}}>0.$

Além disso, por $(**)$, podemos dizer que

$x_{n+1}={\frac {-2007+{\sqrt {\Delta _{n+1}}}}{2}}={\frac {-2007+{\sqrt {2007^{2}-4+4x_{n}}}}{2}}.$

Observe que, neste caso, $x_{n+1}$ é uma raiz de $x_{2}+2007x+1-x_{n}=0$, ou seja, $f(x_{n+1})=x_{n}$ e assim $f^{n+1}(x_{n+1})=f^{n}(x_{n})=0$ (esta última igualdade é válida por hipótese de indução).

Exemplo (OBM 2011 - 3ª Fase - Nível 2)

Para qualquer número natural $N$ de $2k$ dígitos, seja $I(N)$ o número de $k$ dígitos obtido escrevendo os algarismos de ordem ímpar de $N$ da esquerda para a direita e $P(N)$ como o número de $k$ dígitos obtido escrevendo os algarismos de ordem par de $N$ da esquerda para direita. Por exemplo, $I(249035)=405$ e $P(249035)=293$. Provar que não é possível encontrar um natural $N$ de $2k$ algarismos tal que $N=I(N).P(N)$.

Solução: Vamos usar indução em $k$.

• $k = 1$

Aqui $N$ tem $2$ algarismos e por isso podemos escrever $N={\overline {ab}}=10a+b$.

Provaremos que $N>I(N).P(N)(*)$. Para isto, reescreveremos esta expressão de modo equivalente. Observe que

$N>I(N).P(N)\Leftrightarrow 10a+b>ab\Leftrightarrow a(10-b)+b>0$.

Observe que $a>0$ (ele não pode ser igual a zero, pois se ele fosse, $N$ teria apenas um algarismo). Além disso, $0\leq b<10$, de onde segue que a desigualdade é verdadeira.

• Suponha que $(*)$ seja válido para todo $N'$ com $2(k-1)$ dígitos. Provaremos que vale também para os números de $2k$ dígitos.

Com efeito, vamos montar o número com $2k$ algarismos a partir de $N'$. Para isso, vamos adicionar os algarismos $x$ e $y$ à esquerda de $N'$ e formar $N={\overline {xyN'}}=10^{2k-1}x+10^{2k-2}y+N'$.

Queremos mostrar que $N>I(N).P(N)$. Para facilitar a nossa escrita, vamos escrever

$\varepsilon =P(N')$

$\theta =I(N')$.

Observe que $\varepsilon$ e $\theta$ possuem $k - 1$ dígitos cada e por hipótese de indução $N'>\theta \varepsilon$. Além disso, podemos calcular $I(N)$ e $P(N)$ em função do que já temos.

$P(N)={\overline {x\varepsilon }}=x.10^{k-1}+\varepsilon$

$I(N)={\overline {y\theta }}=y.10^{k-1}+\theta$.

Vamos reescrever o que queremos provar de um modo equivalente:

$N>I(N).P(N)\Leftrightarrow$

$\Leftrightarrow 10^{2k-1}x+10^{2k-2}y+N'>(x.10^{k-1}+\varepsilon )(y.10^{k-1}+\theta )\Leftrightarrow$

$\Leftrightarrow 10^{2k-1}x+10^{2k-2}y+N'>10^{2k-2}xy+10^{k-1}(x\theta +y\varepsilon )+\varepsilon \theta (**)$.

Já sabemos pela hipótese de indução que $N'>\theta \varepsilon$. Assim, para mostrarmos $(**)$, basta provarmos que

$10^{2k-1}x+10^{2k-2}y>10^{2k-2}xy+10^{k-1}(x\theta +y\varepsilon )$.

Vamos continuar procurando uma desigualdade equivalente a essa. Se dividirmos ambos os lados por $10^{k-1}$:

$10^{k}x+10^{k-1}y>10^{k-1}xy+(x\theta +y\varepsilon )(***)$.

Como podemos provar isto? Observe que $\varepsilon$ e $\theta$ possuem $k - 1$ algarismos e por isso são menores ou iguais a $10^{k-1}-1$. Com isso, conseguimos fazer aparecer $x\theta +y\varepsilon$ em uma desigualdade:

$x\theta +y\varepsilon \leq x(10^{k-1}-1)+y(10^{k-1}-1)=(10^{k-1}-1)(x+y)$.

Vamos forçar o lado direito de $(***)$ aparecer. Para isto, somaremos $10^{k-1}xy$ em ambos os lados da desigualdade anterior:

$x\theta +y\varepsilon +10^{k-1}xy\leq 10^{k-1}xy+(10^{k-1}-1)(x+y)$.

Se mostrarmos que

$10^{k-1}xy+(10^{k-1}-1)(x+y)<10^{k}x+10^{k-1}y$,

então $(***)$ fica demonstrada. A desigualdade acima equivale a

$10^{k-1}xy+10^{k-1}x<10^{k}x+x+y$.

Observe que

$10^{k-1}xy+10^{k-1}x=10^{k-1}x(y+1)\leq 10^{k-1}x.10=10^{k}x<10^{k}x+x+y.$

Isto prova $(***)$ e portanto a afirmação do enunciado é verdadeira.

Princípio da Indução Generalizado

Seja $P(n)$ uma propriedade dos números naturais. O Princípio da Indução Generalizado estabelece que: se as afirmações

(i) (Base da Indução) $P(n_0)$ é verdadeira;

(ii) (Passo Indutivo) Se $P(n)$ é verdadeira para algum $n \geq n_0$, então $P(n+1)$ também é.

são ambas verdadeiras, então $P(n)$ é válida para qualquer $n \geq n_0$.

Indução Forte

Se as afirmações

(i) $P(n_0)$ é válida;

(ii) Se $P(n_{0}),P(n_{0}+1),P(n_{0}+2)\dots ,P(n)$ são válida então $P(n+1)$ também é válida.

são ambas verdadeiras, então $P(n)$ é válida para qualquer $n \geq n_0$.

Quando devemos usar indução forte? Quando, no passo indutivo, não conseguimos provar $P(n+1)$ apenas usando $P(n)$ e sim usando $P(n_{0}),P(n_{0}+1),P(n_{0}+2)\dots ,P(n)$.

Exemplo (Cone Sul 2003)

Considere a sequência $\{ a_n \}$ definida da seguinte maneira:

$a_1=1$

$a_2=3$

$a_{n+2}=2a_{n+1}a_{n}+1$, para todo inteiro $n \geq 1$.

Provar que a máxima potência de $2$ que divide $a_{4006}-a_{4005}$ é $2^{2003}$.

Solução: Façamos alguns casos particulares.

$a_{3}=2a_{2}a_{1}+1=2.1.3+1=7$

$a_{4}=2a_{3}a_{2}+1=2.7.3+1=43$

$a_{5}=2a_{4}a_{3}+1=2.43.7+1=603$

Para nos ajudar aqui, defina

$A_{n}=a_{n}-a_{n-1},$

para $n\ge 2$ natural. Com isso,

$A_{2}=a_{2}-a_{1}=3-1=2$

$A_{3}=a_{3}-a_{2}=7-3=4$

$A_{4}=a_{4}-a_{3}=43-7=36$

$A_{5}=a_{5}-a_{4}=603-43=560.$

Estes casos particulares nos fazem suspeitar que a maior potência que $A_{2n}$ é $2^n$ e que $2^{n+1}\mid A_{2n+1}$. Vamos usar indução forte em $n$ para mostrarmos estas duas afirmações ao mesmo tempo. Observe que se mostrarmos apenas a primeira afirmação, resolveremos o problema. Mas precisaremos da segunda afirmação para mostrarmos a primeira.

(i) Já fizemos os casos $n=1$ e $n=2$.

(ii) Suponha que ambas as afirmações que queríamos mostrar sejam verdadeiras para todos os valores menores ou iguais a $n$. Provaremos que elas também são válidas também para $n+1$.

Observe que

$A_{2(n+1)}=A_{2n+2}=a_{2n+2}-a_{2n+1}=2a_{2n+1}a_{2n}+1-(2a_{2n}a_{2n-1}+1)=2a_{2n}(a_{2n+1}-a_{2n-1}).$

Para podermos usar a hipótese, precisamos fazer $A_{2n}$ aparecer. Para isso, façamos

$A_{2(n+1)}=2a_{2n}(a_{2n+1}-a_{2n}+a_{2n}-a_{2n-1})=2a_{2n}(A_{2n+1}+A_{2n}).$

Por hipótese de indução, existe $x_{2n}$ ímpar tal que $A_{2n}=2^{n}x_{2n}$ e $x_{2n+1}$ inteiro tal que $A_{2n+1}=2^{n+1}x_{2n+1}(*)$. Com isso,

$A_{2(n+1)}=2a_{2n}(2^{n+1}x_{2n+1}+2^{n}x_{2n})=2^{n+1}a_{2n}(2x_{2n+1}+x_{2n}).(**)$

Podemos afirmar que $a_{2n}(2x_{2n+1}+x_{2n})$ é ímpar? Note que $2x_{2n+1}+x_{2n}$ é ímpar, pois $x_{2n}$ também é. E quanto a $a_{2n}$? Podemos ver que é ímpar pela definição da sequência $\{ a_n \}$.

Desta forma, a maior potência de $2$ que divide $A_{2(n+1)}$ é $2^{n+1}$.

Vejamos agora que $2^{(n+1)+1}\mid A_{2(n+1)+1}$. De fato, de modo análogo ao que fizemos anteriormente

$A_{2(n+1)+1}=A_{2n+3}=2a_{2n+1}(A_{2n+2}+A_{2n+1}).$

Por $(*)$ e $(**)$,

$A_{2n+3}=2a_{2n+1}(2^{n+1}a_{2n}(2x_{2n+1}+x_{2n})+2^{n+1}x_{2n+1})=2^{n+2}a_{2n+1}(a_{2n}(2x_{2n+1}+x_{2n})+x_{2n+1}).$

Desta forma, $2^{(n+1)+1}\mid A_{2(n+1)+1}$. Com isso, a maior potência de $2$ que divide $A_{4006}=a_{4006}-a{4005}$ é $2^{2003}$.

Lugares Para Estudar

• Indução I (POTI - Nível 2)
• Indução II (POTI - Nível 2)
• Problemas Resolvidos (POTI - Nível 2)
• Princípios (POTI - Nível 2)
• O artigo da Revista Eureka 3: O Princípio da Indução (Elon Lages Lima).
• A aula da Semana Olímpica de 2017: Indução (Samuel Feitosa)
• A aula da Semana Olímpica de 2019: Princípio da Indução Finita (Edson Roberto Are)
• A aula da Semana Olímpica de 2019: Princípio da Indução Finita (Kellem Santos)

Vídeos

• Indução I (POTI - Nível 2)
• Indução II (POTI - Nível 2)
• Princípios (POTI - Nível 3)
• Alguns Exercícios Sobre Indução I (POTI 2017)
• Alguns Exercícios Sobre Indução II (POTI 2017)
• Princípio da Indução Finita (POTI 2017)
• Variações do Princípio da Indução Finita (POTI 2017)
• Alerta para o uso correto do método de indução (POTI 2017)

Bibliografia

• MARTINEZ, Fabio Brochero; MOREIRA, Carlos Gustavo; SALDANHA, Nicolau; TENGAN, Eduardo. Teoria dos Números: um passeio com primos e outros números familiares pelo mundo inteiro. Rio de Janeiro: SBM, 2010. 450 p. ISBN 978-85-244-0312-5.