Please use induction to prove this statement:
The sum across Row $n$ of Pascal's triangle equals $2^n$, and the sum of every second entry of Row $n$ is half of that total.
I can evaluate this by direct counting but can't see how to use induction. Thank you!
On
First question by induction:
Base case: Pascal row $0$ is a single copy of $1 = 2^0\quad \checkmark$
Induction: Assume row $n$ total is $2^n$. Then the elements of row $n{+}1$ are each formed by adding two elements of row $n$, and each element of row $n$ contributes to forming two elements of row $n{+}1$. Thus the total for row $n{+}1$ is $2\cdot 2^n = 2^{n+1}$ as required.
Note also that each element of row $n$ contributes once each to an alternating set of the elements of row $n{+}1$, meaning the total of that alternating set is exactly $2^n$, i.e. half the $n{+}1$ row total.
Hint: This all comes down to Pascal's rule.
Namely, for the first part, at $n=k+1$, $$ \sum_{i=0}^{k+1}\binom{k+1}{i}= \sum_{i=0}^{k+1}\binom{k}{i}+\binom{k}{i-1}= \sum_{i=0}^{k}\binom{k}{i}+\sum_{i=1}^{k+1}\binom{k}{i-1}= 2\sum_{i=0}^{k}\binom{k}{i}. $$ Then, use the inductive hypothesis.
The second part is similar, just change the sums to skip every other entry. Due to the request in the comments, I'll write out the details in this direction.
For row $m$, there are $m+1$ terms in that row. If $m$ is even, then $m+1$ is odd, and we take terms $0$, $2$, $4$, $\cdots$, $m-1$ for a total of $\frac{m}{2}$ terms. If $m$ is odd, then $m+1$ is even, and we take terms $0$, $2$, $4$, $\cdots$, $m$ for a total of $\frac{m+1}{2}$ terms.
For $m$ even, the sum is $$ \sum_{i=0}^{\frac{m}{2}}\binom{m}{2i}=\sum_{i=0}^{\frac{m}{2}}\binom{m-1}{2i}+\binom{m-1}{2i-1}=\sum_{i=0}^{\frac{m}{2}-1}\binom{m-1}{2i}+\sum_{i=1}^{\frac{m}{2}}\binom{m-1}{2i-1} $$ Since $\binom{m-1}{2i-1}=\binom{m-1}{(m-1)-(2i-1)}=\binom{m-1}{m-2i}$ (one can check this by writing out the binomial terms with factorials, this sum becomes $$ \sum_{i=0}^{\frac{m}{2}-1}\binom{m-1}{2i}+\sum_{i=1}^{\frac{m}{2}}\binom{m-1}{m-2i}. $$ Then, using the change of variables $m-2i=2j$ (and being sure to change the indices appropriately), we get $$ \sum_{i=0}^{\frac{m}{2}-1}\binom{m-1}{2i}+\sum_{i=0}^{\frac{m}{2}-1}\binom{m-1}{2j}=2\sum_{i=0}^{\frac{m}{2}-1}\binom{m-1}{2i}. $$ Then, apply the inductive hypothesis at $m-2$.
Alternatively, one could have stopped at $$ \sum_{i=0}^{\frac{m}{2}-1}\binom{m-1}{2i}+\sum_{i=1}^{\frac{m}{2}}\binom{m-1}{2i-1} $$ and realized that the lower indices of the binomial expansion include all integers from $0$ to $m-1$. These, sums simplify to $$ \sum_{i=0}^{m-1}\binom{m-1}{i} $$ which we know from the original proof is equal to $2^{m-1}$ (which is half of $2^m$ as desired).
For $m$ odd, the sum is $$ \sum_{i=0}^{\frac{m+1}{2}}\binom{m}{2i}=\sum_{i=0}^{\frac{m+1}{2}}\binom{m-1}{2i}+\binom{m-1}{2i-1}=\sum_{i=0}^{\frac{m+1}{2}-1}\binom{m-1}{2i}+\sum_{i=1}^{\frac{m+1}{2}}\binom{m-1}{2i-1}. $$ Here, the symmetry trick from above doesn't work, but we can see that the lower indices in the binomials include all integers from $0$ to $m-1$. Therefore, these sums are $$ \sum_{i=0}^{m-1}\binom{m-1}{i} $$ which we know from the original proof is equal to $2^{m-1}$ (which is half of $2^m$ as desired).