Hello!(adsbygoogle = window.adsbygoogle || []).push({});

We've got the following to prove by induction:

a) [itex]2n+1\le{2^n}[/itex]

b) [itex]n^2\le{2^n}[/itex]

(It is assumed that 0 is a natural number)

a) This inequality is not valid for [itex]n=1,2[/itex], so to prove the inequality one has to show its validity for all [itex]n\ge{3}[/itex]:

1) [itex]A(3):7\le{8}[/itex] (true)

2) Assume that [itex]A(n)[/itex] is true.

[itex]A(n+1): 2(n+1)+1\le{2^{n+1}}[/itex]

[itex]2(n+1)+1=(2n+1)+2\le{2^n+2}\le{2^{n+1}}[/itex], since for [itex]2^n+2\le{2^{n+1}}[/itex] we have [itex]n\ge{1}[/itex]

Is there a difference if I make the induction step this way?:

2)[itex]A(n+1): 2(2n+1)\le{2^{n+1}}[/itex], so to prove A(n) we must show that [itex]2n+3\le{4n+2}[/itex], which is also true for [itex]n\ge{1}[/itex]

The thing that disturbs me is that if we assume 0 to be a natural number the last inequalities in 2) in both cases do not hold...but I think this case doesn't play a role since we are to prove it for n greater 3...does it?

b) This inequality is invalid for all [itex]n=3[/itex], so to show that the inequality is valid we must show that it is valid for all [itex]n\ge{4}[/itex]

1) [itex]A(4)=16\le{16}[/itex] (true)

2) Assume that [itex]A(n)[/itex] is true.

[itex]A(n+1): (n+1)^2\le{2^{n+1}}[/itex]

[itex](n+1)^2=n^2+2n+1\le{2^n+2n+1}\le{2^{n+1}}[/itex]. The last inequality in this string is equivalent to [itex]2n+1\le{2^n}[/itex], which was proved in a).

Here, equally, the same question...Is there a difference if I do it this way?:

2) [itex]A(n+1): 2n^2\le{2^{n+1}}[/itex]

[itex](n+1)^2=n^2+2n+1\le{n^2+3n-3}\le{n^2+n^2-3}\le{2n^2}[/itex]

**Physics Forums | Science Articles, Homework Help, Discussion**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Prove by induction

**Physics Forums | Science Articles, Homework Help, Discussion**