Mathematical Induction?

Question

n^2 < 2^n for every integer n>5

(the > that is in n>5 has a line under it)

Answer 1

Let say n^2 < 2^n is true

n^2 < 2^n
2 x n^2 < 2 x 2^n
n^2 + n^2 < 2^(n+1) --(1)

(n-1)^2 > 2 where n > 5
n^2 - 2n + 1 > 2
n^2 > 2n + 1
n^2 + n^2 > n^2 + 2n +1
n^2 + n^2 > (n+1)^2
from (1)
(n+1)^2 < 2^(n+1)

When n = 5
5^2 = 25 < 2^5 = 32

So, n^2 < 2^n for every integer n>=5

Answer 2

The line under the > sign means it's a greater-than-or-equal-to sign. That's commonly written as >= when the exact symbol isn't available.

Anyhow, for 5 you check it just by calculating that 25<32.

So the other claim you need to check is "Assume it's true for n. Show that's it's true for n+1." (This is not one of those rare inductive proofs where you'd use the fact for, say, n-1 or some smaller integer.)

Well, since n^2 < 2^n, 2 * n^2 < 2^(n+1).

So if we can check that (n+1)^2 < 2n^2, we're done.

But that's true whenever (n+1)/n is less than the square root of of 2. And THAT happens whenever 1/n is less than 0.414 ...

So there you have it. Reorganize those steps a bit and add some trivial other ones, and it's a proof!

Answer 3

Oh, you mean n^2 < 2^n for every integer n>=5. Use this notation everytime, next time.

Anyway, first part would be to VERIFY. 5^2 < 2^5, which is true.

Next, we ASSUME that the expression above is true for a certain k, which means that n^2 < 2^n, for every integer 5<=n<=k.

Next, we SHOW that this is still true for n = k+1.

(k+1)^2 < 2^(k+1)
k^2 + 2k + 1 < 2^k*2^1
k^2 + 2k + 1 < 2^k + 2^k

Since we know that k^2 < 2^k (because we assumed earlier that its true for 5<=n<=k), we then try to prove that

2k + 1 < 2^k

To do this, we will instead prove that

2k + 1 < k^2
0 < k^2 - 2k -1
k < 1 - sqrt(2) or k > 1 + sqrt(2) [I do hope that you have no problems with quadratic inequalities.]

Since k>=5 is within k>1+sqrt(2), then we have just proven that

2k+1 < k^2, thus

2k+1 < 2^k

Since both k^2 and 2k +1 < 2^k then we have proven that

k^2 + 2k +1 < 2^k + 2^k.

So now, we CONCLUDE that the expression n^2 < 2^n for all integer n>= 5, is true for all n.

Answer 4

To prove something by mathematical induction, you must establish two things:
1. That the statement is true for n=1 (or in this case, n=5)
2. That if a statement is true for a given value n, it follows that it must also be true for n+1

Starting with Part 1, let's prove your statement for n=5:

5²<2^5
25<32

Now for Part 2. Assume that the statement is true for a value n, and examine how you'd change it to evaluate it for n+1:

To get from n² to (n+1)², you have to add 2n+1, because (n+1)²=n²+2n+1.
To get from 2^n to 2^(n+1), you add 2^n, because 2^n+2^n=2*2^n=2^(n+1).
Now, as long as 2n+1<=2^n, you're adding at least as much to the right side as the left, and so the right side will always remain greater than or equal to the left. I leave the proof that 2n+1<=2^n to you.

Answer 5

Let the given statement be P(n)

For n=5
n^2=25<2^5 Hence P(5) is true.

Let P(k) be true (k>5)
Hence, it is established that k^2<2^k.

Now observe that
k>5
k-1>4
Squaring both sides:
k^2-2k+1>16
k^2-15>2k
2k+1 Adding k^2 to both sides
k^2 + 2k+1<2k^2-14
(k+1)^2<2k^2-14<2k^2
(k+1)^2<2k^2
Now, using k^2<2^k
(k+1)^2<2*2^k
(k+1)^2<2^(k+1)
But this is the statement for P(k+1), which has been proven true.
Hence, P(5) is true, and P(k+1) is true whenever P(k) is true for k>5.

Thus, the statement n^2 < 2^n has been proven for n>=5 by the Principle of mathematical Induction.

Note: The > with a line under it is actually >=, or greater than/equal to.

Hope this helps!!

Answer 6

Just because something says "for all integers at least 5" doesn't mean you have to jump on the induction bandwagon. There are other possible techniques. For this problem, for instance, you can use calculus.

Let f(x)=2^x-x^2. We want to show that f(x) is strictly positive for x at least 5. f(5)=7>0, so it suffices to show that f '(x) is positive for x at least 5. (This would show that f(x) is an increasing function; so since f(5)>0, f(x)>0 for all larger x.) f '(x)=2^x*log(2)-2x. Again, f '(5)=32*log(2)-10 > 12, since log(2)>0.69 . So now it suffices to show that f ''(x)>0 for x at least 5 (this suffices for the same reason as above). f ''(x)=2^x*(log(2))^2-2. f ''(5)=32*(log(2))^2-2>13. But f ''(x) is clearly an increasing function, so we are done.

Answer 7

Proof by induction has two parts. Firstly prove true for the lowest allowed value of n; this is usually very easy. Secondly prove that if it is true for some value of n, say n = p, then it must be true for one more n = p + 1. This is the harder part. You will need to rewrite each side of the inequality with n replaced by p + 1 and simplify. Then somehow use the assumption of it being true for p to prove true for p + 1. When you have done both parts you simply add "therefore true for all n > 5 by induction".

Answer 8

a proof is available at

http://rbmix.com/math/mathinduct/mthin.php