ちょっとした線形写像の質問です。数列$\{A_n}$が、$a_1=1$. $a_2=2$. $a_3=3$. $a_{n+3}=a_{n+2}+a_n \left(n=1.2.3...\right)$を満たす。この時、$$a_n=\sum_{k=0}^{[\dfrac{n+1}{3}]}{}_{n+1-2k}\mathrm{C}_k$$が成り立つことを示せ。ただし、$[\dfrac{n+1}{3}]$は、$\dfrac{n+1}{3}$の整数部分を表す。

数学的帰納法で解くのが一番賢い方法だと思いますが、ぱっとひらめいたものが割とよかったので、それを紹介します。

白と黒の石が$n$個ある。黒が2個だけ連続した置き方であるとき

（白黒白や白黒黒黒白の並びが無く、白黒黒白しかない）、

意思の並べ方の場合の数を考える。

この場合の数を$a_n$とする。

$a_1=1, a_2=2, a_3=3$となる。

$(ⅰ)$

$n+3$この石の並べ方$a_{n+3}$について、

白〇〇〇………〇〇〇

　　　　$n+2$個の並べ替え$a_{n+2}$

黒黒白〇〇………〇〇

　　　　　$n$個の並べ替え$a_n$

の二通りがあり、漸化式$a_{n+3}=a_{n+2}+a_n$が得られる。

$(ⅱ)$

さらに、$a_n$について、次のことが言える。

黒は2個連続したものしかないから、偶数個である。

よって、白を$n-2k$個、黒を$2k$

　　　　　　　$n-2k$個

　白　白　白　………　白　白　白

↑　↑　↑　↑………↑　↑　↑　↑

　　　　　　　 $n-2k+1$個

この矢印の中から$k$個を選び、矢印一個にたいして2個の黒を入れると、条件を満たす並び方が得られる。よって、${}_{n-2k+1}\mathrm{C}_k$通り。

このような$k$は$0$から$[\frac{n+1}{3}]$まで存在するため、その和をとって

$$a_n=\sum_{k=0}^{[\frac{n+1}{3}]} {}_{n+1-2k}\mathrm{C}_k$$

$(ⅰ)(ⅱ)$より、両者が一致する。