I am solving a probability question and I have come across a recursive formula that is hard to prove. The recursive formula goes like this: $$a_1=2$$ $$a_n = a_{(n-1)} + a_{(n-2)} + ... + a_{(n-k)},\;\;\;\;n\geq k+1$$
where $n$ is the number of flips of a fair coin and $k$ stands for successive $k$ heads. The term $a_n$ stands for the number of ways of flipping a coin $n$ times without getting $k$ successive heads.
Now I want to prove that $a_n \leq c^n$ for some $c<2$, and $n\geq (k+1)$.
I thought about proving by induction but you reach the induction hypothesis and things get hairy from there. Is there any other method to prove this?