[Aritmética: Teoria dos Números – Números naturais – Princípio da Indução Finita]
Usando o Princípio da Indução Finita, mostre que [tex]\sf n^2\ \textless \ 2^n[/tex] para todo n natural, n > 4.
Usando o Princípio da Indução Finita, mostre que [tex]\sf n^2\ \textless \ 2^n[/tex] para todo n natural, n > 4.
More Questions From This User See All
Lista de comentários
Verified answer
Algumas proposições prévias
[Proposição 1] Para todo n natural, n > 1, temos [tex]2<2^n.[/tex]
[Demonstração] Usando o Princípio da Indução Finita.
[tex]\Longleftrightarrow\quad 2\cdot 2<2\cdot 2^k\\\\ \Longleftrightarrow\quad 4<2^{k+1}[/tex]
e como 2 < 4, segue pela transitividade da relação < que
[tex]\Longrightarrow\quad 2<4<2^{k+1}\\\\ \Longrightarrow\quad 2<2^{k+1}[/tex]
Logo, a desigualdade vale para n = k + 1.
Portanto, [tex]2<2^n[/tex] para todo n natural, n > 1. □
[Proposição 2] Para todo n natural, n > 2, temos [tex]2n+1<2^n.[/tex]
[Demonstração] Usando novamente o Princípio da Indução Finita.
[tex]2<2^k[/tex]
Some 2k + 1 a ambos os membros:
[tex]\Longleftrightarrow\quad (2k+1)+2<(2k+1)+2^k\\\\ \Longleftrightarrow\quad 2k+3<(2k+1)+2^k\\\\ \Longleftrightarrow\quad 2(k+1)+1<(2k+1)+2^k\qquad\mathrm{(i)}[/tex]
Por outro lado, pela H.I., segue que
[tex]2k+1<2^k[/tex]
Some [tex]2^k[/tex] a ambos os membros:
[tex]\Longleftrightarrow\quad (2k+1)+2^k<2^k+2^k\\\\ \Longleftrightarrow\quad (2k+1)+2^k<2\cdot 2^k\\\\ \Longleftrightarrow\quad (2k+1)+2^k<2^{k+1}\qquad\mathrm{(ii)}[/tex]
Por (i) e (ii), podemos novamente aplicar a transitividade da relação <, e temos
[tex]\Longrightarrow\quad 2(k+1)+1<(2k+1)+2^k<2^{k+1}\\\\ \Longrightarrow\quad 2(k+1)+1<2^{k+1}[/tex]
Logo, a desigualdade vale para n = k + 1.
Portanto, [tex]2n+1<2^n,[/tex] para todo n natural, n > 2. □
Finalmente, vamos à proposição apresentada nesta tarefa.
Mostrar que n² < 2ⁿ, para todo n natural, n > 4
[Proposição 3] Para todo n natural, n > 4, temos [tex]n^2<2^n.[/tex]
[Demonstração] Aplicando novamente o Princípio da Indução Finita.
[tex]2k+1<2^k[/tex]
Some k² a ambos os membros:
[tex]\Longleftrightarrow\quad k^2+2k+1<k^2+2^k\\\\ \Longleftrightarrow\quad (k+1)^2<k^2+2^k\qquad\mathrm{(iii)}[/tex]
Por outro lado, da H.I., segue que
[tex]k^2<2^k[/tex]
Some [tex]2^k[/tex] a ambos os membros:
[tex]\Longleftrightarrow\quad k^2+2^k<2^k+2^k\\\\ \Longleftrightarrow\quad k^2+2^k<2\cdot 2^k\\\\ \Longleftrightarrow\quad k^2+2^k<2^{k+1}\qquad\mathrm{(iv)}[/tex]
Por (iii) e (iv), aplicando novamente a transitividade da relação <, finamente concluímos que
[tex]\Longrightarrow\quad (k+1)^2<k^2+2^k<2^{k+1}\\\\ \Longrightarrow\quad (k+1)^2<2^{k+1}[/tex]
Logo, a desigualdade vale para n = k + 1.
Portanto, [tex]n^2<2^n,[/tex] para todo n natural, n > 4. ■
Dúvidas? Comente.
Bons estudos! :-)
✅ Após realizar a demonstração, concluímos que a proposição "n² < 2^n, para todo n natural, n > 4" de fato é verdadeira, isto é:
[tex]\Large\displaystyle\text{$\begin{gathered}\boxed{\boxed{\:\:\:\bf (k + 1)^{2} < 2^{k + 1}\:\:\Longrightarrow\:\:\textrm{Verdadeira}\:\:\:}}\end{gathered}$}[/tex]
Seja a proposição:
[tex]\Large\displaystyle\text{$\begin{gathered} n^{2} < 2^{n},\:\:\forall n \in \mathbb{N},\:n > 4\end{gathered}$}[/tex]
Ora, se "n" pertence aos naturais e "n" é maior que "4", então podemos reescrever a proposição como:
[tex]\Large\displaystyle\text{$\begin{gathered} n^{2} < 2^{n},\:\:\forall n \in \mathbb{N},\:n \geq 5\end{gathered}$}[/tex]
Para provar esta proposição pelo método de indução, devemos:
Seja:
[tex]\Large\displaystyle\text{$\begin{gathered} n = 5\end{gathered}$}[/tex]
Então, temos:
[tex]\Large \text {$\begin{aligned}5^{2} & < 2^{5}\\5\cdot5 & < 2\cdot2 \cdot 2\cdot 2\cdot 2\\ 25 & < 32\end{aligned} $}[/tex]
Desta forma, percebemos que a base de indução de fato é verdadeira, ou seja:
[tex]\Large\displaystyle\text{$\begin{gathered} P(5)\:\:\Longrightarrow\textrm{Verdadeiro}\end{gathered}$}[/tex]
[tex]\Large\displaystyle\text{$\begin{gathered} P(K)\:\Longrightarrow\: k^{2} < 2^{k}\end{gathered}$}[/tex]
Admitindo que:
[tex]\Large\displaystyle\text{$\begin{gathered} P(K)\:\:\Longrightarrow \:\textrm{Verdadeira}\end{gathered}$}[/tex]
Devemos provar a veracidade de:
[tex]\Large\displaystyle\text{$\begin{gathered} P(K + 1)\:\:\Longrightarrow\:\:(k + 1)^{2} < 2^{k + 1}\end{gathered}$}[/tex]
Então:
[tex]\Large\displaystyle\text{$\begin{gathered}{\bf I}\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\: (k + 1)^{2} < 2^{k + 1}\end{gathered}$}[/tex]
Para provarmos que "P(K + 1)" é verdadeira, devemos desenvolver algebricamente o primeiro membro da inequação "I", até chegarmos ao segundo membro, levando em consideração a hipótese de indução. Para isso, fazemos:
[tex]\Large \text {$\begin{aligned}(k + 1)^{2} & = k^{2} + 2k + 1\:\:\:\:(\textrm{se}\:1 < 5)\\& < k^{2} + (2k + 5)\:\:\:\:(\textrm{se}\:k \geq 5)\\& = k^{2} + (2k + k)\\& = k^{2} + 3k\\& = k^{2} + k\cdot3\:\:\:(\textrm{se}\:3 < 5)\\& < k^{2} + k\cdot 5\:\:\:(\textrm{se}\: k \geq5)\\& = k^{2} + k\cdot k\\& = k^{2} + k^{2}\\& = 2k^{2}\\& = k^{2}\cdot2\:\:\:(\textrm{se}\: k^{2} < 2^{k})\\& < 2^{k}\cdot 2\\& = 2^{k + 1}\end{aligned} $}[/tex]
Portanto, está provado que:
[tex]\Large\displaystyle\text{$\begin{gathered} P(K + 1)\:\:\Longrightarrow \:\:\textrm{Verdadeira}\end{gathered}$}[/tex]
Uma vez que:
[tex]\Large\displaystyle\text{$\begin{gathered} (k + 1)^{2} < 2^{k + 1}\end{gathered}$}[/tex]
[tex]\LARGE\displaystyle\text{$\begin{gathered} \underline{\boxed{\boldsymbol{\:\:\:Bons \:estudos!!\:\:\:Boa\: sorte!!\:\:\:}}}\end{gathered}$}[/tex]
Saiba mais: