How to prove equality between two terms How can I prove that:
$$
\sum_{i=0}^{N}(i+1)\binom{N}{i}(3^{N-i}) = 4^{N-1}(N+4)
$$
One can see that the above is true for any case manually, but how do I prove it formally? I have no idea how to go about it.
 A: $$\begin{align*}
\sum_{i=0}^N(i+1)\binom{N}i3^{N-i}&=\sum_{i=0}^Ni\binom{N}i3^{N-i}+\sum_{i=0}^N\binom{N}i3^{N-i}\\\\
&\overset{(1)}=N\sum_{i=0}^N\binom{N-1}{i-1}3^{N-i}+\sum_{i=0}^N\binom{N}i3^{N-i}\\\\
&=N\sum_{i=0}^{N-1}\binom{N-1}i3^{N-1-i}+\sum_{i=0}^N\binom{N}i3^{N-i}\\\\
&\overset{(2)}=N(1+3)^{N-1}+(1+3)^N\\\\
&=N4^{N-1}+4^N\\\\
&=(N+4)4^{N-1}\;.
\end{align*}$$
Step $(1)$ uses the identity $i\dbinom{N}i=N\dbinom{N-1}{i-1}$, which is easily proved either algebraically or combinatorially. Step $(2)$ uses the binomial theorem.
A: There are a few general techniques (see Petkovsek, Wilf and Zeilberger's "A = B") but nothing that will work in all cases. In a case like yours, induction should work, but it could get to be quite a mess.
Let's start with the binomial theorem:
$$
\sum_{0 \le i \le N} \binom{N}{i} z^i = (1 + z)^N
$$
This is just a polynomial in $z$, so it is permissible to do the following:
$$
\begin{align*}
\frac{d}{d z} \left(z \sum_{0 \le i \le N} \binom{N}{i} z^i\right)
  &= \frac{d}{d z} \left(\sum_{0 \le i \le N} \binom{N}{i} z^{i + 1} \right) \\
  &= \sum_{0 \le i \le N} (i + 1) \binom{N}{i} z^i \\
  &= (1 + z)^N + N z (1 + z)^{N - 1}
\end{align*}
$$
You get your sum as:
$$
\begin{align*}
3^N \sum_{0 \le i \le N} (i + 1) \binom{N}{i} 3^{-i}
  &= 3^N \left(\left( 1 + \frac{1}{3} \right)^N 
       + N \frac{1}{3} \left(1 + \frac{1}{3} \right)^{N - 1} \right) \\
  &= 4^{N - 1}(N + 4)
\end{align*}
$$
