Recurrence Relation: Robot can climb flight of n stairs 1 stair and land on either foot; 2 stairs & land on its left; or 3 stairs & land on its right

Question

(a) Find a recurrence relation (with initial conditions) for the number of ways a robot can climb a flight of n stairs if at each step it can go up $1$ stair and land on either foot; or go up $2$ stairs and land on its left foot; or go up $3$ stairs and land on its right foot.

(b) Use your recurrence relation to find the number of ways the robot can climb a flight of 50 stairs.

(c) Repeat the question if additionally, the robot cannot land on its left foot twice in a row.

(d) Use your recurrence relation to find the number of ways the robot can climb a flight of 50 stairs.

Answer 1

$\require{enclose}$

a) Let's start with the initial conditions (base cases)
The subscripts on L and R indicate the distance traveled
$R_1$ means 1 stair with the right foot
$L_1$ means 1 stair with the left foot
$R_2$ means 2 stair with the right foot
$L_3$ means 3 stairs with the left foot

• $a_0=1$ (Only 1 way to climb $0$ stairs)
• $a_1=2$ (Climb 1 stair with either foot)
• $a_2=5$
  • $R_2$ (Go up 2 stairs & land on the right foot)
  • $R_1R_1$, $L_1L_1$, $R_1L_1$ and $L_1R_1$ (4 ways to combine Left & Right foot movements of 1 stair)

The robot has 3 cases for whether it goes 1 stair, 2 stairs or 3

• $2a_{n-1}$ ($2$ ways to go up 1 stair & land on either foot, follow with an $n-1$ length sequence)
• $a_{n-2}$ ($1$ way to go 2 stairs & land on the left foot, follow with an $n-2$ length sequence since we used up 2 stairs)
• $a_{n-3}$ ($1$ way to go up 3 stairs and land on right foot)

Putting it altogether: $$a_n = 2a_{n-1} + a_{n-2} + a_{n-3}$$

Let's verify $a_3$ by counting all the cases going 3 stairs

$R_3$, $L_2L_1$, $L_2R_1$, $L_1L_2$, $R_1L_2$ ($5$ cases so far)
Plus $2^3=8$ combinations of $L_1$ and $R_1$ to go a total 3 stairs moving 1 stair at a time
$a_3=5+8$
$=13$

and using the recurrence relation & plugging in base cases gives the same answer
$a_3 = 2a_{3-1} + a_{3-2} + a_{3-3}$
$=2a_{2} + a_{1} + a_{0}$
$=2*5 + 2 + 1$
$=13$

b) Evaluating recurrence relations is tedious by hand, but in Wolfram Mathematica they are dead simple to input & evaluate

(* Putting "a[n]=" after function definition speeds up calculation & avoids recursion overflow *)
a[n_]:= a[n]=2a[n-1]+a[n-2]+a[n-3]
a[0]=1;
a[1]=2;
a[2]=5;

Now Evaluate it:
a[50]
Outputs: 156424759849575406340

c) The restriction that it can't do 2 left feet in a row complicates it significantly. Any time a left move is made, we must follow it with a right foot move to avoid 2 left feet in a row

There are $6$ cases in the recurrence relation but we can combine the $2$ for $b_{n-3}$

• $b_{n-1}$ (1 stair with the right foot)
• $b_{n-3}$ (3 stairs with the right foot)
• $b_{n-2}$ (1 stair left foot, then follow with 1 stair right to avoid 2 left in a row. Used up 2 stairs so follow with valid $n-2$ sequence)
• $b_{n-3}$ (2 stairs left, then follow with 1 stair right)
• $b_{n-4}$ (1 stair left, follow with 3 stairs on the right foot)
• $b_{n-5}$ (2 stairs with left, follow with 3 stairs on the right)

Putting it together: $$b_n = b_{n-1} + b_{n-2} + 2b_{n-3} + b_{n-4} + b_{n-5}$$

Now counting the base cases also gets harder

• $b_0=1$ (1 way to go up no stairs)
• $b_1=2$ ($R_1$ or $L_1$ Simply right or left, no way to get 2 lefts in a row with just 1 step)
• $b_2=4$ ($R_2$, $R_1R_1$, $R_1L_1$ and $L_1R_1$. This excludes $L_1L_1$)
• $b_3=8$
  • 5 cases going 1 step: $R_1R_1R_1$, $R_1R_1L_1$, $R_1L_1R_1$, $L_1R_1R_1$, $L_1R_1L_1$
  • 2 cases using left 2 stairs: $L_2R_1$ and $R_1L_2$
  • 1 case going up 3 stairs on the right: $R_3$
• $b_4=17$ (There are $6$ kinds of cases based on how many steps traveled (ways to add 1, 2 & 3 to equal 4, avoiding 2 lefts in a row) )
  • 1 1 1 1 = 1 stair each move
    • 8 valid cases: $R_1R_1R_1R_1$, $R_1R_1R_1L_1$, $R_1R_1L_1R_1$, $R_1L_1R_1R_1$, $R_1L_1R_1L_1$, $L_1R_1R_1R_1$, $L_1R_1R_1L_1$, $L_1R_1L_1R_1$
    • This is probably the hardest one
    • Start by enumerating all 16 combinations of L and R
    • Imagine you're counting in binary with R=$0$ and L=$1$. So $R_1R_1R_1L_1=0001$ and $R_1L_1L_1R_1=0110$
      I've left them in the order of smallest to largest when read left to right
    • $R_1R_1R_1R_1$, $R_1R_1R_1L_1$, $R_1R_1L_1R_1$, $R_1R_1L_1L_1$ $R_1L_1R_1R_1$, $R_1L_1R_1L_1$, $R_1L_1L_1R_1$, $R_1L_1L_1L_1$, $L_1R_1R_1R_1$, $L_1R_1R_1L_1$, $L_1R_1L_1R_1$, $L_1R_1L_1L_1$, $L_1L_1R_1R_1$, $L_1L_1R_1L_1$, $L_1L_1L_1R_1$, $L_1L_1L_1L_1$
    • Cross out the ones with $2$ $L$'s
    • $R_1R_1R_1R_1$, $R_1R_1R_1L_1$, $R_1R_1L_1R_1$, $\enclose{horizontalstrike}{ R_1R_1L_1L_1, }$ $R_1L_1R_1R_1$, $R_1L_1R_1L_1$, $\enclose{horizontalstrike}{ R_1L_1L_1R_1, }$ $\enclose{horizontalstrike}{ R_1L_1L_1L_1, }$ $L_1R_1R_1R_1$, $L_1R_1R_1L_1$, $L_1R_1L_1R_1$, $\enclose{horizontalstrike}{ L_1R_1L_1L_1, }$ $\enclose{horizontalstrike}{ L_1L_1R_1R_1, }$ $\enclose{horizontalstrike}{ L_1L_1R_1L_1, }$ $\enclose{horizontalstrike}{ L_1L_1L_1R_1, }$ $\enclose{horizontalstrike}{ L_1L_1L_1L_1 }$
    • This leaves you with the 8 from above
  • 1 2 1=1 stair followed by 2 stairs then 1 stair
    • 1 valid case: $R_1L_2R_1$ (Left foot going 2 stairs forces the surrounding steps to be with the right)
  • 2 1 1=2 stairs 1st then 1 stair and 1 stair
    • 2 valid cases: $L_1R_1R_1$ and $L_2R_1L_1$
  • 1 1 2=1 stair then 1 stair then 2 stairs
    • 2 valid cases: $R_1R_1L_2$ and $L_1R_1L_2$
  • 1 3=1 stair then 3 stairs
    • 2 valid cases: $R_1R_3$ and $L_1R_3$
  • 3 1=3 stairs then 1 stair
    • 2 valid cases: $R_3R_1$ and $R_3L_1$
  • Notice we skip 2 2 since left foot is the only foot than can move 2 at a time we are avoiding 3 lefts in a row

d) Again, hard to by hand, but using Mathematica:

b[n_]:= b[n] = b[n-1] + b[n-2] + 2b[n-3] + b[n-4] + b[n-5]
b[0]=1;
b[1]=2;
b[2]=4;
b[3]=8;
b[4]=17;

Now Evaluate it: b[50]
Outputs: 10020502088013274