Question with recurrence - Check my answer and suggest better ideas

Question

Every morning when he gets up, Oria leaves the house for a walk. he walks exactly $n$ steps. He can walk only forward, right, or left, and he will never turn left immediately after he turned right, and he will never turn right immediately after he turned left.

In how many ways can Oria walk?

My answer

I decided to do this with recurrence. Let $f(n)$ be the correct answer.

If the first step Oria took was to the right, then he can either go straight (and after that he will have $f(n-2)$ options) or go right again, and then again he can either go straight (for $f(n-3)$ options) or right again and so on and so forth...

This brought me to the conclusion that if the first step Oria took was to the right, then he has $(\sum_{i=2}^{n-1}f(n-i))+1$ options. This is the same if the first step was to the left (since its symmetric), and if the first step was straight, then he has $f(n-1)$ options.

So overall:

$f(n)=2((\sum_{i=2}^{n-1}f(n-i))+1)+f(n-1)$

The problem here is that now I can't find a solution. I'm supposed to get a recurrence relation that I can solve, I need to find a way to get rid of that $\sum$

Answer 1

For simplicity, we use F,R,and L to denote the forward, right, and left directions.

Let $f(n)$ denote the number of ways Oria can walk in exactly $n$ steps. Oria can walk in $f(n-1)$ ways if the last step is F. Oria can walk in $f(n-1)$ ways if the last two steps are LL,RR,FL. Oria can walk in $f(n-2)$ ways if the last two steps are FR.

The recurrence relation is thus $$f(n)=2f(n-1)+f(n-2)$$ with the initial terms $f(0)=1$ and $f(1)=3$

Note that this recurrence is linear and can hence be solved using standard characteristic polynomials. Since \begin{equation} \begin{pmatrix} f(n)\\ f(n-1) \end{pmatrix}= \begin{pmatrix} 2 & 1\\ 1&0 \end{pmatrix} \begin{pmatrix} f(n-1)\\ f(n-2) \end{pmatrix} \end{equation} The characteristic polynomial of $$\begin{pmatrix} 2 & 1\\ 1&0 \end{pmatrix}$$ is $x^2-2x-1$ and $f(n)$ is $$a(1+\sqrt{2})^n+b(1-\sqrt{2})^n$$ where $a$ and $b$ can be solved to be $\frac{1+\sqrt{2}}{2}$ and $\frac{1-\sqrt{2}}{2}$, respectively, using the initial terms. Hence, $$f(n)=\frac{1}{2}[(1+\sqrt{2})^{n+1}+(1-\sqrt{2})^{n+1}]$$

Note: This problem can be found on page 203 in R.Stanley's Enumerative Combinatorics Vol. $1$}.

Answer 2

Suggestion: I would try to approach each possibility this way:

If you draw a tree for this you will notice that for every n increment, for every 3 ways, n+1 will have 3+2+2=7 ways and for every 2 ways, n+1 will have 3+2=5 increments.

So:
for n=0 then f(0)=0 ways
for n=1 then f(1)=3 ways
for n=2 then f(2)=3+2+2=7 ways
for n=3 then f(3)=(3+2+2)+(3+2)+(3+2)=17 ways
for n=4 then f(4)=((3+2+2)+(3+2)+(3+2))+((3+2+2)+(3+2))+((3+2+2)+(3+2))=41 ways and so on...
Perhaps you can find the recurrence relation without summation with these relationships from n to n+1.