Question with recurrence - Check my answer and suggest better ideas 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$

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.
