# Wrong proof using Mathematical induction

I wrongly tried to prove the sequence $$a_n=\frac{n}{2^n}$$ is increasing. (It is obvious the sequence is decreasing but I didn't realized it at first and I was proving it is increasing by mistake!)

So I used mathematical induction to prove $$a_{n}\leq a_{n+1}$$:

$$n=1 : a_1=\frac{1}{2} \leq a_2=\frac{1}{2}$$

Assume $$n=k : a_k \leq a_{k+1}$$

Now we prove for $$n=k+1 : a_{k+1} \leq a_{k+2}$$ or $$\frac{k+1}{2^{k+1}} \leq \frac{k+2}{2^{k+2}}$$

We assumed $$a_k \leq a_{k+1} \rightarrow \frac{k}{2^k} \leq \frac{k+1}{2^{k+1}}$$

So $$k (2^{k+1}) \leq 2^k (k+1)$$ multiply both side by $$2$$ and we obtain : $$k(2^{k+2}) \leq 2^{k+1} (k+1)$$ then add $$2^{k+2}$$ to the sides: $$(k+1) 2^{k+2}\leq 2^{k+1}(k+3) \leq 2^{k+1}(k+2)$$ Hence: $$\frac{k+1}{2^{k+1}} \leq \frac{k+2}{2^{k+2}} \rightarrow a_{k+1} \leq a_{k+2}$$

So I proved the sequence $$a_n$$ is increasing with mathematical induction But as I said earlier it is wrong and it is decreasing actually. But why this method "mathematical induction" works perfectly well here? I am sure I did exactly the steps for that (first proved it works for $$n=1$$ then assumed it works for $$n=k$$ and conclude it works for $$n=k+1$$) It is really strange for me to see how mathematical induction confirm the sequence is increasing . Am I missing something?

• $2^{k+1}(k+3)\le2^{k+1}(k+2)$? – player3236 Sep 24 '20 at 11:49
• Ah. I messed up here! good catch – Soheil Sep 24 '20 at 11:51
• @MathLearner $a_1= \frac{1}{2} , a_2=\frac{2}{4}$ – Soheil Sep 24 '20 at 13:38

$$2^{k+1}(k+3)\leq 2^{k+1}(k+2)$$
This is false. In fact $$2^{k+1}(k+2)<2^{k+1}(k+3)$$. So this is where your inductive argument breaks down, and doesn't prove the result.