1. Proof by induction help??

k

2. It would help if you showed what you've done so far and where you're stuck!

3. k

4. Originally Posted by Intsecxtanx
Prove by induction that if n > 1, then $2^n$ < 1 + n $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.

$2^2$ < 1 + 2 ( $2^{2-1}$)
4 < 1 + 2(2)
4 < 5 which is true

Inductive Hypothesis: Assume P(k) is true for some k.
$2^k$ < 1 + k $2^{k-1}$
$2^{k+1}$ < 2 ( 1 + k $2^{k-1}$)
2 $(2^k)$ < 2 + k( $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!
Your basic step is correct. That is, you assume P(k) is true. Assuming P(k) is true means we assume that $2^k < 1+k2^{k-1}$ for some arbitrary positive integer k.

Now, we want to prove that P(k+1) is true. This means we want to prove that the following inequality: $2^{k+1} < 1 + (k+1)2^{k-1+1}$ holds. We shall prove it by using our assumption:

$2^{k+1} = 2 \cdot 2^k$. Now, we shall use the fact that $a\cdot 2^k < b\cdot 2^k$ for any positive a,b such that a<b. How will we use this? -- We know that the minimal value of k is 2, and therefore the minimal value of $k+1$ is 3. Therefore, $2\cdot 2^k < (k+1)\cdot 2^k$.

--> $2^{k+1} < (k+1)2^k < 1+ (k+1)2^k$, and this is exactly what we were looking to prove: $2^{k+1}<1+(k+1)2^k$. Therefore P(k+1) is true and we are done.