Problem
COM-B1-M10-P019 Steps \(1\) and \(3\)
#19
★★★☆☆ Level 3 of 5
In how many ways can one climb \(12\) stairs if each move is \(1\) or \(3\) stairs?
The last step has length \(1\) or \(3\).
Let \(a_n\) be the number of ways. Then \(a_n=a_{n-1}+a_{n-3}\), with \(a_0=1\), \(a_1=1\), \(a_2=1\). We get \(a_3=2\), \(a_4=3\), \(a_5=4\), \(a_6=6\), \(a_7=9\), \(a_8=13\), \(a_9=19\), \(a_{10}=28\), \(a_{11}=41\), \(a_{12}=60\).
Shows a recurrence that skips \(a_{n-2}\).