# Why are these two expressions different in this induction problem?

Prove with $n \ge 1$:

$$\frac{3}{1\cdot2\cdot2} + \frac{4}{2\cdot3\cdot4}+\cdots+\frac{n+2}{n(n+1)2^n} = 1 - \frac{1}{(n+1)2^n}$$

First, I prove it for $n=1$: $$\left(\frac{1+2}{1(1+1)2^1} = 1-\frac{1}{(1+1)2^1}\right) \implies \left(\frac{3}{4} = 1- \frac{1}{4}\right) \implies \left(\frac{3}{4} = \frac{3}{4}\right)$$ Which is true.

So I will now assume this: $$\frac{3}{1\cdot2\cdot2} + \frac{4}{2\cdot3\cdot2}+\cdots+\frac{n+2}{n(n+1)2^n} = 1 - \frac{1}{(n+1)2^n}$$

And I want to prove it for $n+1$, i.e:

$$\frac{3}{1\cdot2\cdot2} + \frac{4}{2\cdot3\cdot2}+\cdots+\frac{n+2}{n(n+1)2^n} + \frac{n+3}{(n+1)(n+2)2^{n+1}} = 1 - \frac{1}{((n+1)+1)2^{n+1}}$$

This is how I tried to prove it:

$$\frac{3}{1\cdot2\cdot2} + \frac{4}{2\cdot3\cdot2}+\cdots+\frac{n+2}{n(n+1)2^n} + \frac{n+3}{(n+1)(n+2)2^{n+1}} =$$

$$1 - \frac{1}{(n+1)2^n} + \frac{n+3}{(n+1)(n+2)2^{n+1}}$$

Before continuing, I usually like to grab a calculator, give a value to $n$ and evaluate my current expression with the expression I want to reach. If both values are equal, it means I'm doing okay.

So I took $n=5$ and evaluated the expression I want to reach:

$$1 - \frac{1}{(5+2)\cdot2^5+1} = \frac{447}{448}$$ Then, still with $n = 5$ I evaluated my current expression: $$1 - \frac{1}{(5+1)\cdot2^5}+\frac{5+3}{(5+1)(5+1)\cdot2^{5+1}} = \frac{575}{576}$$

So I got $\frac{447}{448}$ for the expression I want to reach and $\frac{575}{576}$ for what I got so far. Something went wrong.

My problem with this is that I haven't done any calculations yet. All my steps so far were rather mechanical - things I always do with mathematical induction.

Maybe I simply evaluated them wrongly. But I can't see it - I've tested it many times already.

Why are both expressions different? They should be the same.

-
In the last term of the last displayed equation, looks like one of those $5+1$s should be a $5+2$. – Gerry Myerson Nov 27 '12 at 6:09
The second is $\dfrac{447}{448}$ after Gerry's correction. – Jonas Meyer Nov 27 '12 at 6:13
@GerryMyerson: You're right. Thank you. Do post the answer :) – Zol Tun Kul Nov 27 '12 at 6:14
why is the denominator in the second term $2\cdot 3\cdot 2$? It should be $2\cdot3 \cdot 4$. – André Nicolas Nov 27 '12 at 6:15
@AndréNicolas: Ah! You're right! Fixing now. – Zol Tun Kul Nov 27 '12 at 6:18

Elevating comment to answer, at suggestion of OP:

In the last term of the last displayed equation, there is a $5+1$ where there should be a $5+2$. Jonas Meyer notes that this correction gets rid of the discrepancy.

-
Confirmed - it does work now. Thank you. – Zol Tun Kul Nov 27 '12 at 6:22

There is a flaw in the logic in this posting:

begin quote:

First, I prove it for $n=1$: $$\left(\frac{1+2}{1(1+1)2^1} = 1-\frac{1}{(1+1)2^1}\right) \implies \left(\frac{3}{4} = 1- \frac{1}{4}\right) \implies \left(\frac{3}{4} = \frac{3}{4}\right)$$ Which is true.

end of quote

This is not valid reasoning. You're saying "Let's prove $A$, as follows: If $A$ then $3/4 = 3/4$, which is true." Very well then, I shall prove that Socrates was John F. Kennedy: If Socrates was John F. Kennedy, then Socrates died in 1963, and hence, Socrates was mortal. Which is true." To say "If B then A. And A is true. Therefore B." is a standard erroneous form of reasoning. Writers on logic since the time of Aristotle have identified this as a fallacy. A correct way of reasoning is this: $$\frac{1+2}{1(1+1)2^1} = \frac34 = 1 - \frac14 = 1-\frac{1}{(1+1)2^1}.$$ Therefore the proposition in case $n=1$.

And then you repeat the same fallacy in your inductive step.

You should write "$=$" between things ALREADY KNOWN TO BE EQUAL. Then when you write $$A = B = C = \cdots = Z,$$ then that proves that $A=Z$. You should not write $$A = Z$$ therefore $$B=Y$$ therefore $$C=X$$ etc. etc. etc. etc.
Therefore $$3=3$$ which is true. Therefore $A=Z$.

-
Ah! You're right about the $n=1$ case. But I'm a bit confused about the inductive step case. I mean, since I am assuming that $\frac{3}{1\cdot2\cdot2} + \frac{4}{2\cdot3\cdot2}+\cdots+\frac{n+2}{n(n+1)2^n} = 1 - \frac{1}{(n+1)2^n}$ then I do know that $\frac{3}{1\cdot2\cdot2} + \frac{4}{2\cdot3\cdot2}+\cdots+\frac{n+2}{n(n+1)2^n} + \frac{n+3}{(n+1)(n+2)2^{n+1}} = 1 - \frac{1}{(n+1)2^n} + \frac{n+3}{(n+1)(n+2)2^{n+1}}$, I guess. – Zol Tun Kul Nov 27 '12 at 6:25