I'm trying to prove the following...
3^n > 3n + 1 for all positive integers n > 1... (*)
I'm using induction on n to prove the above..
n = 2: 3^2 = 9 > 3(2) + 1 = 7
Assume (*) is true for some value of n > 1 (Inductive Hypothesis)
Need to show it is also true for n + 1
That is need to show:
3^(n+1) > 3(n+1) + 1
3^(n+1) > 3n + 4
3 * 3^n > 3 * (3n+1) (By I.H.) = 9n + 3 this is not by the IH, this is by the distributive law
My question is, do I just say that 9n + 3 > 3n + 4 at this point and conclude that (*) is true? Or is there some other justification I need to show.
NO! Almost, but not quite. What you need to show is that, for
, this will complete your proof.