Recurrence Relation of a series I know this would seem lame, but I need to ask this.
I was trying to solve some recurrence based problems and I came across this series.
$1,2,4,7,12,\dots$
Question was: To find the recurrence relation and solve it.
I found the recurrence relation as follows: 
$T(n) = T(n-1) + T(n-2) + 1$
where, $T(1) = 1 , T(2) = 2$
I tried to solve it, but I could not succeed.
Any kind of help would be appreciated.
p.s.-
This recurrence relation looks somewhat similar to Fibonacci Series Recurrence Relation. So anything related to that?
 A: Rewrite this relationship under the form:
$$ (T_{n} +1)=(T_{n-1}+1) + (T_{n-2}+1)$$
Setting $U_n=T_n+1$, you have the Fibonacci-like sequence:
$$ U_{n}=U_{n-1} + U_{n-2}  \ \ \text{with Initial Values} \ \ \ U_1=2 \ \ \text{and} \ \ U_2=3$$
That is easily solved under the classical form:
$$U_n=A \Phi^n + B \Psi^n$$
for fixed $A=(5+3\sqrt{5})/10$ and $B=(5-3\sqrt{5})/10$, $\Phi$ and $\Psi$ being the golden ratio and its conjugate, resp.
Important edit: I just realized that sequence $U_n=2,3,5,8,13,\cdots $ is plainly the ordinary Fibonacci sequence shifted by 2: $U_n=F_{n+2}$.
Thus a neat answer to your question is
$$T_n=F_{n+2}-1 \ \ \ (1) $$
An explicit formula for $T_n$ is immediately obtained by plugging in (1) the classical explicit Lucas formula for $F_n$.
A: The general solution of $$T_n=T_{n-1}+T_{n-2}+a$$ is given by $$T_n=-a+c_1 F_n+c_2 L_n$$ where appear both Fibonacci and Lucas numbers.
I was typing when Jean-Marie's answer came. So, I stop here.
A: Just to add a general point since you say you are doing a set of recurrence relation problems. You often get a linear recurrence relation with an extra term involving $n$, eg $u_{n+1}=2u_n+f(n)$. The first step is to find a particular solution $p_n$ that deals with the extra term, then the general solution is $u_n=v_n+p_n$ where $v_n$ satisfies the same relation without the extra term $v_{n+1}=2v_n$.
There is no guaranteed way of finding the particular solution. Often $f(n)$ is a polynomial in $n$. In that case $p_n$ is usually another polynomial of the same degree. If you cannot find it quickly by trial and error, then you can put in a general expression like $a+bn$ and solve for $a,b$.
