Proof by induction for $2^{n+1} < 1 + (n+1)\times 2^n$ for $n \geq 1$

Question

I have to prove the predicate in the title. I've did the cases for $P(1)$ and assumed that it is true for all $P(k)$. I am stuck at the step for the predicate $P(k+1)$:

$2^{k+2} < 1 + (k+2)\times 2^{k+1}$

Answer 1

Is there a particular reason why you want to prove it by induction? It seems much more natural to prove it directly: since $n\geq 1$, we have $1+(n+1)2^n\geq 1+(1+1)2^n=1+2^{n+1}$.

Answer 2

The case for $n=1$ is trivial. Now, suppose it's true for some $n\in \mathbb{N}$, that's to say, our induction hypothesis is $$2^n(n+1)+1> 2^{n+1}.$$ Then, let's prove that it's true for $n+1$: \begin{equation} \begin{split} 2^{n+1}(n+2)+1 &=2^{n+1}(n+1)+2^{n+1}+1 \\ & = 2\cdot 2^n(n+1) +2^{n+1}+2-1 \\ & = 2(2^n(n+1)+1) +2^{n+1}-1 \\ & > 2\cdot 2^{n+1} +2^{n+1}-1 \quad \text{(induction hypothesis)} \\ & = 2^{n+2} +(2^{n+1}-1) \\ & > 2^{n+2} \quad \text{(because } 2^{n+1}>1 \text{ for all } n\in \mathbb{N}) \end{split} \end{equation}

Answer 3

You can rewrite the inequation as

$$0<1+(n-1)2^n$$

and it feels hard to... not think it true.

If you cannot live without induction,

$$0<1+(n-1)2^n<1+n2^{n+1}$$ because the terms in the RHS are no smaller.