Induction question (1 Viewer)

SunnyScience · Feb 25, 2012

Prove 3^n > n^2

Thanks

(hopefully this posts okay - first time using my phone

)
Sent from my LG-P990 using Tapatalk

SunnyScience · Feb 25, 2012

furthermore,

(1+p)^n > 1 +np for n>1 and p>o

Sent from my LG-P990 using Tapatalk

deswa1 · Feb 25, 2012

I don't have time to post a solution but I'll outline my method and maybe someone else can help/you can do it.

1. Prove for n=1
2. Assume true for n=k (3^k>k^2)
3. We need to prove that 3^(k+1)>(k+1)^2. This is the same as proving that 3^(k+1)-(k+1)^2>0
4. Split 3^(k+1) into 3(3^k) and then use the inequality established in step two.
5. Simplify and prove that its greater than zero.

Cl324 · Feb 25, 2012

$3^k > k^2 \\ 3^{k+1}> (k+1)^2$
so basically you try to make $3^{k+1}- (k+1)^2 >0$
$3^k\times3 > k^2\times3\\ 3^{k+1}> 3k^2\\ 3^{k+1}- (k+1)^2 > 3k^2- (k+1)^2\\ 3^{k+1}- (k+1)^2 > 2k^2- 2k -1$
since $2k^2- 2k -1$ is a parabola with coefficient > 1 and its discriminant is <0, the parabola will always be greater than zero
and hence $3^{k+1}- (k+1)^2 >0$

there are various ways of doing induction equalities, but i think manipulating the original equation to make it look like the second equation is the easiest

SunnyScience · Feb 25, 2012

Cl324 said:
$3^k > k^2 \\ 3^{k+1}> (k+1)^2$
so basically you try to make $3^{k+1}- (k+1)^2 >0$
$3^k\times3 > k^2\times3\\ 3^{k+1}> 3k^2\\ 3^{k+1}- (k+1)^2 > 3k^2- (k+1)^2\\ 3^{k+1}- (k+1)^2 > 2k^2- 2k +1$
since $2k^2- 2k +1$ is a parabola with coefficient > 1 and its discriminant is >0, the parabola will always be greater than zero
and hence $3^{k+1}- (k+1)^2 >0$

there are various ways of doing induction equalities, but i think manipulating the original equation to make it look like the second equation is the easiest

thanks for that

too me a few minutes to work out your steps - but great!

kingkong123 · Feb 26, 2012

Cl324 said:
$3^k > k^2 \\ 3^{k+1}> (k+1)^2$
so basically you try to make $3^{k+1}- (k+1)^2 >0$
$3^k\times3 > k^2\times3\\ 3^{k+1}> 3k^2\\ 3^{k+1}- (k+1)^2 > 3k^2- (k+1)^2\\ 3^{k+1}- (k+1)^2 > 2k^2- 2k -1$
since $2k^2- 2k -1$ is a parabola with coefficient > 1 and its discriminant is <0, the parabola will always be greater than zero
and hence $3^{k+1}- (k+1)^2 >0$

the discri

there are various ways of doing induction equalities, but i think manipulating the original equation to make it look like the second equation is the easiest

$\\\Delta = (-2)^{2}-4(2\times-1)\\=4+8\\=12\\\nless 0$ ???

$\textup{The way to do it is prove that }2k^{2}-2k-1> 0 \textup{ for } k> \frac{1+\sqrt{3}}{2}\textup{ and }\\k<\frac{1-\sqrt{3}}{2}. \textup{ This satisfies the statement only for }k\geq 2.\textup{ You can then sub in }k=0\textup{ and }k=1\textup{ to prove the statment is true for all }k\geq 0$

IamBread · Feb 26, 2012

Cl324 said:
$3^k > k^2 \\ 3^{k+1}> (k+1)^2$
so basically you try to make $3^{k+1}- (k+1)^2 >0$
$3^k\times3 > k^2\times3\\ 3^{k+1}> 3k^2\\ 3^{k+1}- (k+1)^2 > 3k^2- (k+1)^2\\ 3^{k+1}- (k+1)^2 > 2k^2- 2k -1$
since $2k^2- 2k -1$ is a parabola with coefficient > 1 and its discriminant is <0, the parabola will always be greater than zero
and hence $3^{k+1}- (k+1)^2 >0$

there are various ways of doing induction equalities, but i think manipulating the original equation to make it look like the second equation is the easiest

The discriminant is >0

nightweaver066 · Feb 26, 2012

Just doing n = k + 1

$3^{k + 1} > (k + 1)^2$

$3^{k + 1}$

$= 3 \times 3^k$

$> 3k^2$

$= k^2 + 2k + 1 + 2k^2 - 2k - 1$

$= (k + 1)^2 + 2k^2 - 2k -1$

$Consider 2k^2 - 2k - 1 = 0$

$2k^2 - 2k -1 = 0$

$k = \frac{2 \pm \sqrt{12}}{4}$

$= \frac{1 \pm \sqrt{3}}{2}$

$\therefore 2k^2 - 2k - 1 < 0 $ when $ \frac{1 - \sqrt{3}}{2} < k < \frac{1 + \sqrt{3}}{2}$

$-0.366 < k < 0.289$

$\therefore (k + 1)^2 + 2k^2 - 2k -1 > (k + 1)^2 $ for positive integers k$$

$\therefore 3^{k + 1} > (k + 1)^2$

Cl324 · Feb 26, 2012

nightweaver066 said:
Just doing n = k + 1

$3^{k + 1} > (k + 1)^2$

$3^{k + 1}$

$= 3 \times 3^k$

$> 3k^2$

$= k^2 + 2k + 1 + 2k^2 - 2k - 1$

$= (k + 1)^2 + 2k^2 - 2k -1$

$Consider 2k^2 - 2k - 1 = 0$

$2k^2 - 2k -1 = 0$

$k = \frac{2 \pm \sqrt{12}}{4}$

$= \frac{1 \pm \sqrt{3}}{2}$

$\therefore 2k^2 - 2k - 1 < 0 $ when $ \frac{1 - \sqrt{3}}{2} < k < \frac{1 + \sqrt{3}}{2}$

$-0.366 < k < 0.289$

$\therefore (k + 1)^2 + 2k^2 - 2k -1 > (k + 1)^2 $ for positive integers k$$

$\therefore 3^{k + 1} > (k + 1)^2$

Yeah whoops sorry I just did a quick calculation in my head. ^ Shouldve done it on paper but thats how you're suppose to do it

Induction question (1 Viewer)

SunnyScience

Member

SunnyScience

Member

deswa1

Well-Known Member

Cl324

Member

SunnyScience

Member

kingkong123

Member

IamBread

Member

nightweaver066

Well-Known Member

Cl324

Member

Users Who Are Viewing This Thread (Users: 0, Guests: 1)