Find the generating function for the number of ways to climb n stairs

Question

Problem : Write the recurrence relation for the sequence $\left( a _ { 0 } , a _ { 1 } , \ldots \right)$ where $a _ { n }$ is the number of ways we can climb $n$ stairs so that in each step we climb 1 or 3 stairs. Write the generating function for this sequence.

---

Solution : The recurrence relation is $a_{n+3} = a_{n+2} + a_n$. The sequence we obtain as $\left( c _ { n } \right) -$ $\left( b _ { n } \right) - \left( a _ { n } \right) ,$ where $\left( c _ { n } \right)$ is $\left( a _ { n } \right)$ shifted to the right by $3 ,$ and $\left( b _ { n } \right)$ is $\left( a _ { n } \right)$ shifted to the right by 1 is $( - 1,0,0,0 , \ldots )$. Thus, $x ^ { 3 } F ( x ) - x ^ { 2 } F ( x ) - F ( x ) = - 1 ,$ and hence, $F ( x ) = \frac { 1 } { 1 - x ^ { 2 } - x ^ { 3 } }$

I don't seem to understand why $c_n$ is $a_n$ shifted to the right by 3, and $b_n$ is $a_n$ shifted to the right by 1. Furthermore I don't understand why the sequence would be $( - 1,0,0,0 , \ldots )$.

Answer 1

We can write the recurrence relation as $$ a_n=a_{n-1}+a_{n-3}\quad (a_0=1, a_1=1,a_2=1) $$ for $n\geq 3$. We can make the change of index $n\to n+3$ to rewrite the recurrence relation as $$ a_{n+3}=a_{n+2}+a_n\quad (n\ge 0).\tag{1} $$ At this point multiply both sides of (1) by $x^n$ and sum on $n\geq 0$ (where we put $A(x)=\sum_{n=0}^\infty a_n x^n$ to get that $$ \frac{A(x)-a_0-a_1x-a_2x^2}{x^3}=\frac{A(x)-a_0-a_1x}{x^2}+A(x) $$ Solve for $A(x)$ to get that $$ A(x)=\frac{1}{1-x-x^3}. $$ Note that this answer makes sense the problem is equivalent to the number of ways to write $n$ as an ordered sum of ones and threes and this formulation is also apparent from writing $$ A(x)=\frac{1}{1-(x+x^3)}=\sum_{m=0}^\infty (x+x^3)^m. $$ and taking the coefficient of $x^n$ of the RHS.

Answer 2

The point is that you can go in step of ones up to any $n$.
So you can go to $n+3$ from $n+2$ in only one way: through a step of 1.
You can also go to $n+3$ from $n$ with a step of 3, but you shall not add the possibility to go there by three consecutive 1-steps, because this way is already accounted in the sequence $n \to n+1 \to n+2 \to n+3$. Thus the recurrence is actually $$ a_{\,n + 3} = a_{\,n + 2} + a_{\,n} $$

But the construction reported is obscure to me as well. I would do in the following way.

Being a third grade recurrence, you need to fix three initial conditions.
These shall be $$ a_{\,n} = 0\quad \left| {\,n \le 0} \right.\quad a_{\,1} = 1\quad a_{\,2} = 1\quad a_{\,3} = 2 $$ and the recurrence shall be better written so as to include the initial conditions as $$ a_{\,n} = a_{\,n - 1} + a_{\,n - 3} + \left[ {n = 1} \right] + \left[ {n = 3} \right]\quad \left| {\;0 \le n} \right. $$ where $[P]$ denotes the Iverson bracket $$ \left[ P \right] = \left\{ {\begin{array}{*{20}c} 1 & {P = TRUE} \\ 0 & {P = FALSE} \\ \end{array} } \right. $$

Then $$ \eqalign{ & 0 = \sum\limits_{0\, \le \,n} {a_{\,n} \,x^{\,n} } - \sum\limits_{0\, \le \,n} {a_{\,n - 1} \,x^{\,n} } - \sum\limits_{0\, \le \,n} {a_{\,n - 3} \,x^{\,n} } - \sum\limits_{0\, \le \,n} {\left[ {n = 1} \right]\,x^{\,n} } - \sum\limits_{0\, \le \,n} {\left[ {n = 3} \right]\,x^{\,n} } = \cr & = G(x) - x\sum\limits_{0\, \le \,n} {a_{\,n - 1} \,x^{\,n - 1} } - x^{\,3} \sum\limits_{0\, \le \,n} {a_{\,n - 3} \,x^{\,n - 3} } - x - x^{\,3} = \cr & = G(x)\left( {1 - x - 2x^{\,3} } \right) - x - x^{\,3} \quad \Rightarrow \cr & \Rightarrow \quad G(x) = {{x + x^{\,3} } \over {1 - x - x^{\,3} }} = {1 \over {1 - \left( {x + x^{\,3} } \right)}} - 1\quad \Rightarrow \cr & \Rightarrow \quad \left\{ {a_{\,n} } \right\} = \left\{ {{\rm 0}{\rm , 1}{\rm , 1}{\rm , 2}{\rm , 3}{\rm , 4}{\rm , 6}{\rm , 9}{\rm , 13}{\rm , 19}{\rm , 28}{\rm , 41}{\rm , } \cdots } \right\} \cr} $$

So that the given $F(x)$ equals $G(x)+1$