Let's say that we want to fill n squares each lying on one line, with plus'es, minus'es, or zero's in such a way that plus never lies next to minus. The question is - in how many ways can we fill these squares? For example when $n=2$ the answer is 7, pictures below represent each of possible fillings.
I've managed to answer this question... almost. At first I assumed that we are filling squares respectively from left to right. Now let's also assume that we have filled some squares and there are $k$ left. It is easy to see that if we have filled last square with $0$ then we can fill reminding squares in $f_k$ ways, where $f_n$ is the number of possible fillings of $n$ squares.
There are three types of fillings now:
1)The first square is filled with $0$
2)First $m-1$ squares are filled with + or - and m'th square with $0$, $0<m<n-1$
3)We fill all of the squares with + or -
4)We fill all of the $n-1$ squares with + or - and the last one with $0$
Using the mentioned facts we end up with the recursive formula for $f_n$ which is:
$$f_n=f_{n-1}+2\sum_{m=1}^{n-2}f_{n-m-1}+2+2=f_{n-1}+2\sum_{m=1}^{n-2}f_m+4$$
$$f_1=3$$
$$f_2=7$$
Now I wanted to get rid of summations
$$f_{n+1}-f_{n}=(f_{n}+2\sum_{m=1}^{n-1}f_m+4)-(f_{n-1}+2\sum_{m=1}^{n-2}f_m+4)=f_n+f_{n-1}$$
Now we end up with pretty nice recursive formula for $f_n$ similar to formula for Fibonacci numbers:
$$f_n=2f_{n-1}+f_{n-2}$$
$$f_1=3$$
$$f_2=7$$
Unfortunately I'm not good in solving recursive functions so my questions are:
1)Can we solve this problem in easier way?
2)How can we solve this recursion?
Thanks for all the help.
You are doing well. Now you have a homogeneous recurrence relation with constant coefficients. The usual technique is to assume a solution of the form $r^n$ and substitute that into your relation, getting $r^2=2r+1$. You can solve this to get two values of $r$, which we can call $r_1,r_2$. The general solution is $ar_1^n+br_2^n$ and you evaluate $a,b$ from your initial conditions.