I have this summation:
$$ s_n=\sum_{k=0}^n {n-k \choose k}$$
and I wanted to prove that $s_{n+1}=s_n+s_{n-1}$ for $n \ge 2$.
So to start of with I had $ s_n=\sum_{k=0}^n {n-k \choose k}$ and $s_{n-1}=\sum_{k=0}^{n-1} {n-k-1 \choose k}$. I also found the identity that ${n-1 \choose k-1}+{n-1 \choose k}= {n\choose k}$.
But I am struggling to get any further to combine the two sums into one and rearrange to get $ s_{n+1}=\sum_{k=0}^{n+1} {n-k+1 \choose k}$. Could anyone help? Thank you!
Let's change the index $k\to k-1$ in the sum for $s_{n-1}$. Let's do it step by step: Let $j=k+1$, so $k=j-1$. Making this substitution we get $$s_{n-1}=\sum_{k=0}^{n-1}{n-1-k\choose k}=\sum_{j-1=0}^{n-1}{n-1-(j-1)\choose j-1}=\sum_{j=1}^{n}{n-j\choose j-1}.$$ we can just replace again $j$ by $k$ since this is just an index, so we have: $$s_{n-1}=\sum_{k=1}^n{n-k\choose k-1}.$$ So, \begin{align*}s_n+s_{n-1}&=\sum_{k=0}^n{n-k\choose k}+\sum_{k=1}^n{n-k\choose k-1}\\ &={n-0\choose 0}+\sum_{k=1}^n{n-k\choose k}+\sum_{k=1}^n{n-k\choose k-1}\\ &=1+\sum_{k=1}^n{n-k\choose k}+{n-k\choose k-1}\end{align*}
Now, you can use your identity, getting ${n-k\choose k}+{n-k\choose k-1}={n-k+1\choose k}$. So, $$s_n+s_{n-1}=1+\sum_{k=1}^n{n-k+1\choose k}$$
Now, convince yourself that the RHS is $s_{n+1}$