I'm a high school teacher and students had to see the pattern I have below but they didn't have to prove it. However, an intrepid student asked me to prove it and I am stumped. I scoured the internet but I couldn't find any help. Please help me get started! The identity is below. F0=0, F1=1, F2=1, F3=2, ..., Fn=nth Fibonacci number.
(nC0)(Fk)+(nC1)(Fk+1)+(nC2)(Fk+2)+...+(nCn)(Fk+n) = Fk+2n