Csdrhrt

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 )$.

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 $ngeq 3$. We can make the change of index $nto n+3$ to rewrite the recurrence relation as
$$
a_{n+3}=a_{n+2}+a_nquad (nge 0).tag{1}
$$
At this point multiply both sides of (1) by $x^n$ and sum on $ngeq 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.

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} = 0quad left| {,n le 0} right.quad a_{,1} = 1quad a_{,2} = 1quad 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 = sumlimits_{0, le ,n} {a_{,n} ,x^{,n} } - sumlimits_{0, le ,n} {a_{,n - 1} ,x^{,n} } - sumlimits_{0, le ,n} {a_{,n - 3} ,x^{,n} }
- sumlimits_{0, le ,n} {left[ {n = 1} right],x^{,n} } - sumlimits_{0, le ,n} {left[ {n = 3} right],x^{,n} } = cr
& = G(x) - xsumlimits_{0, le ,n} {a_{,n - 1} ,x^{,n - 1} } - x^{,3} sumlimits_{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)}} - 1quad 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$