<s>[INST] Inductive proof of $\sum_{i=0}^{n} 2^{-i} \binom{n}{i} = \left(\frac{3}{2} \right)^n$ 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.
 [/INST] 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$.
</s>