1

I am trying to prove by induction on $n$ the following theorem:

$$\sum_{i=0}^{n} 2^{-i} \binom{n}{i} = \left(\frac{3}{2} \right)^n$$

For my inductive step I have: $$\sum_{i=0}^{n+1} 2^{-i} \binom{n+1}{i}$$

$$\sum_{i=0}^{n} 2^{-i} \binom{n+1}{i} + \frac{1}{2^{-(n+1)}}$$

Using this identity: $\binom{n+1}{i} = \binom n i + \binom{n}{i-1}$: $$\sum_{i=0}^{n} 2^{-i} \binom{n}{i} + \sum_{i=0}^{n} 2^{-i} \binom{n}{i-1} + \frac{1}{2^{-(n+1)}}$$

$$\left( \frac{3}{2} \right)^n + \frac 1 2\sum_{k=1}^{n} 2^{-k} \binom{n}{k} + \frac{1}{2^{-(n+1)}}$$

$$\left( \frac{3}{2} \right)^n + \frac 1 2 \left[ \left( \frac{3}{2} \right)^n - 1\right] + \frac{1}{2^{-(n+1)}}$$

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

Here I am stuck and I cannot find my mistake.

jaynp
  • 2,151
  • 2
    Not what the question is asking, but here is a non-inductive proof. By the binomial theorem, $(1/2+1)^n=\sum_{i+j=n} \binom{n}{i} (1/2)^i(1)^j$. Simplify and relabel terms. – Aaron Aug 13 '13 at 05:08
  • Most probably the OP hasn't yet proved Newton's Binomial Theorem...which requires induction. – DonAntonio Aug 13 '13 at 12:17

2 Answers2

1

The problem is with the subscript handling for
$$\sum_{i=0}^{n} 2^{-i} \binom{n}{i-1}.\tag{1}$$ Expression (1) is equal to $$\sum_{i=1}^{n} 2^{-i} \binom{n}{i-1},$$ which is equal to $$\frac{1}{2}\sum_{i=0}^{n} 2^{-(i-1)} \binom{n}{i-1}.\tag{2}$$ Let $j=i-1$. We get that (2) is equal to $$\frac{1}{2}\sum_{j=0}^{n-1} 2^{-j} \binom{n}{j}.$$ Sum to $n$ instead, but to keep things unchanged subtract $\frac{1}{2^n}$. We get $$\frac{1}{2}\left(\frac{3}{2}\right)^n -\frac{1}{2^{n+1}}.$$ Now we are finished. For the last term cancels the $\frac{1}{2^{n+1}}$ term you had at the end. And the $\frac{1}{2}\left(\frac{3}{2}\right)^n$ combines with the $\left(\frac{3}{2}\right)^n$ you already have, and we end up with $(1.5)\left(\frac{3}{2}\right)^n$, that is, $\left(\frac{3}{2}\right)^{n+1}$.

André Nicolas
  • 507,029
1

Because under "Using this identity: ...", there is a term $2^{-0} \binom{n}{-1}$, which should be 0 if the identity holds. When you substitute $k=i-1$ or $i = k+1$, the second summation should become

$$\begin{align*} &\frac{1}{2}\sum_{k=-1}^{n-1}2^{-k}\binom{n}{k}\\ =&\frac{1}{2}\sum_{k=0}^{n}2^{-k}\binom{n}{k}-2^{-(n+1)}\binom{n}{n}\\ =&\frac{1}{2}\left(\frac{3}{2}\right)^n - \frac{1}{2^{n+1}} \end{align*}$$

and the latter term above cancels with your last term of $\frac{1}{2^{n+1}}$ (Yea, I guess your last term is wrong too).

Of course I have written the undefined $\binom{n}{-1}$ above, where I should not. Therefore to be safe, use the recursive identity only for $1 \le i \le n$, and also $\binom{n+1}{0} = \binom{n}{0} = 1$.

peterwhy
  • 22,256