Below is a proof claiming to prove that the sum of a row on Pascal's Triangle is equal to 2x the sum of the row before it. The key here was to use Pascal's Identity.
I understand the general concept, but i just can't get how the second line has: \begin{align}\sum_{k=1}^{n-1}\binom{n-1}{k-1} =\sum_{k=0}^{n-2}\binom{n-1}{k}\end{align} And then the third line has: \begin{align}\sum_{k=0}^{n-2}\binom{n-1}{k} + 1 = \sum_{k=0}^{n-1}\binom{n-1}{k}\end{align}
Are there some algebraic laws that we can use to manipulate sigma notations? I can follow what's happening, but the logical reasoning is escaping me in these two spots. Thanks!
The Proof: \begin{align} \sum_{k=0}^{n}\binom nk&=1+\sum_{k=1}^{n-1}\binom nk +1 =1+\sum_{k=1}^{n-1}\binom{n-1}k+\sum_{k=1}^{n-1}\binom{n-1}{k-1}+1 \\ & = 1+\sum_{k=1}^{n-1}\binom{n-1}k+\sum_{k=0}^{n-2}\binom{n-1}{k}+1 \\ &=\sum_{k=0}^{n-1}\binom{n-1}k+\sum_{k=0}^{n-1}\binom{n-1}{k}=2\sum_{k=0}^{n-1}\binom{n-1}{k} \end{align}
The first one is just manipulating the indices of the sum. It might make it more clear to say: suppose $\ell = k-1$. Then as $k$ goes from $1$ to $n-1$, $\ell$ goes from $0$ to $n-2$, and so $$\sum_{k=1}^{n-1} \binom{n-1}{k-1} = \sum_{\ell=0}^{n-2} \binom{n-1}{\ell}.$$ Of course the choice of what to name your index is unimportant, so we can replace $\ell$ by $k$ if we want and write $\sum_{k=0}^{n-2} \binom{n-1}{\ell}$.
For the second equality, notice that the sum on the left differs from the sum on the right by exactly one term. The left side is missing the term $\binom{n-1}{n-1}$. But this binomial coefficient is equal to $1$, so both sides of the equation are equal.