Mathematical Induction?

Question

Proof by induction:

3n (less than or equal to) 3^n
n = element of all natural numbers

Answer 1

To proof a conjecture by Induction you must follow the steps:
a) confirm that it is true for a initial value.... p(1) is true
b) write a theorem connecting p(k) with p(k+1)...
If p(k) is true, them p(k+1) is true
c) proof the theorem written in b)
d) now you have the conclusion: p(n) is true for n natural numbers

In your case, this get:

a) it is true for n=1 because 3(1) <= 3^1
b) if 3k <= 3^k, then 3(k+1) <= 3^(k+1)
c) proof of b)
3k <= 3^k adding 3 to both side...
3k + 3 <= 3^k + 3 factoring first member...
3(k+1) <= 3^k + 3 now we can change the 3 in the second member by a convenient number and greater than 3... this number is 2(3^k)
3(k+1) <= 3^k + 2(3^k) and we finally get
3(k+1) <= 3(3^k) or 3(k+1)<= 3^(k+1) ... as we wanted to proof.

Then we can conclude 3n <= 3^n for natural numbers.

Answer 2

Clearly this is true for n=1
If it is true for some n, then for n+1
3(n+1) ≤ 3^(n+1) => 3n+3 ≤ 3*3^(n) => n+1 ≤ 3^n which is clearly true for all n and the proof is done.


Doug

Answer 3

it is true for 1

now let's imagine it's true for n, and show it for n+1:
3(n+1) vs. 3^(n+1)
3n + 3 vc. 3^n+3^n*2
3n<=3^n (since it holds for n)
3<=3^n*2 (for every n>=1)
so 3n + 3 <= 3^n+3^n*2 QED

Answer 4

get A-level books