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

There is a mistake in your argument. You wrote:

$$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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.