I have some trouble with an induction proof for the following problem.
There is a vending machine that only takes coins of value 1 and 5 respectively. Let $S_n$ be the number of different sequences of coins such that their sum is equal to $n$. (5,1,1) and (1,5,1) counts as two different sequences with sum equal to 7. Prove by induction that $S_n = S_{n-1} + S_{n-5} \forall n \geq 6$.
$S_1=S_2=S_3=S_4=1$ because the only possible sequences for these sums are (1), (1,1), (1,1,1), and (1,1,1,1). $S_5 = 2$ because (1,1,1,1,1) and (5) are the two possible sequences with sum equal to 5.
A combinatorial proof would be: Consider the last element of a sequence whose sum is $n$. It can either be a coin of value 1 or a coin of value 5. If we remove this element from the sequence, the sum of the remaining sequence is either $n-1$ and then there are $S_{n-1}$ different sequences with this sum, or the sum of the remaining sequence is $n-5$ and then there are $S_{n-5}$ different sequences with this sum. Hence, $S_n = S_{n-1}+S_{n-5}$.
However, I am not sure how to prove the recurrence by induction. The base case is easy, though. $S_6 = S_5 + S_1 = 1 + 2$ and the sequences are (1,5), (5,1), and (1,1,1,1,1,1). The induction hypothesis must be $S_k = S_{k-1}+S_{k-5}$ for all $k \leq n$.