# Mathematical Induction?

I understand how to do regular problems using mathematical induction, but now my teacher assigned us harder problems that we haven't learned yet.

Use mathematical induction to prove that n < 2^n whenever n is a positive integer.

Relevance

First prove the base case, n=1: 1 < 2^1 = 2 is true.

Now, suppose that n < 2^n. We need to prove that n+1 < 2^(n+1).

We know n < 2^n, so n + 1 < 2^n + 1

< 2^n + 2^n (since for n positive 2^n > 1)

= 2^(n+1)

So n+1 < 2^(n+1) also.

So, by induction, n < 2^n for every positive integer n.

• For n=1: n<2^n {1<2}

For n=2: n<2^n {2<4}

Assuming P(n) = n, hence P(n) < 2^n

Now, we need to prove that P(n+1) < 2^(n+1).

P(n+1) = n+1 <2^n + 1

Considering R.H.S:

2^n + 1 < 2^n.2 as 2^n > 1 (for n>0).

Hence, P(n+1) < 2^(n+1)

Proved.

• n < 2^n

lim. n =>0

0>1

let n be e

e< 2^e

ln e < e ln2

1 < e ln2

now, let n be 1

1 < 2^1

1 < 2

It is now possible to induce that in all cases where n is an integer that n will be smaller than 2^n

• prove n=1 is easy. (1 < 2^(1) is true)

assume n=k is true, then

Left-Hand-Side

= k+1

< 2^k + 1 ......................( k < 2^k is true)

<2^k +2^k ......................( 2^k > 1 when k > 1)

=2 (2^k)

=2^(k+1)

=Right-Hand-Side

so, k+1 < 2^(k+1)

Hence, we know that when it is true for n=k, it is true for n=k+1

By mathematical induction, it is true for n >= 1 (positive integer)

• Anonymous

assume n=k is true, then

Left-Hand-Side

= k+1

< 2^k + 1 ......................( k < 2^k is true)

<2^k +2^k ......................( 2^k > 1 when k > 1)

=2 (2^k)

=2^(k+1)

=Right-Hand-Side

so, k+1 < 2^(k+1)

Hence, we know that when it is true for n=k, it is true for n=k+1

• Its a useless chapter.

• you must have mr. sutton ..lol