Originally Posted by
Intsecxtanx Prove by induction that if n > 1, then $\displaystyle 2^n$ < 1 + n $\displaystyle 2^{n-1}$
Basis step: I must first verify that the given propositions P(n) are true for n = 0.
However, if n > 1, then the smallest possible value of n = 2.
I must first prove that P(2) is true for n = 2.
$\displaystyle 2^2$ < 1 + 2 ($\displaystyle 2^{2-1}$)
4 < 1 + 2(2)
4 < 5 which is true
Inductive Hypothesis: Assume P(k) is true for some k.
$\displaystyle 2^k$ < 1 + k $\displaystyle 2^{k-1}$
$\displaystyle 2^{k+1}$ < 2 ( 1 + k$\displaystyle 2^{k-1}$)
2$\displaystyle (2^k)$ < 2 + k($\displaystyle 2^k$)
Inductive step: Prove that P(k+1) is true
****(THIS IS WHERE I'M STUCK)****
Once the three steps have been completed, P(n) is true for all n
If P(n) isn’t true for all n, there exists a least counterexample, say k. By the Basis Step, this k is not 0, so k > = 1. but then k-1 > 0 and for k-l the proposition is true
Thank you for your help and time!