I'm trying to solve the following recurrence relation:
$F(n) = F(n -1) + F(n -2) + Θ(n)$ for $n > 1$, and
$Θ(n) = c_1n + c_2$ , where $c_1, c_2 > 0$
and with two initial conditions $F(0) = 0$, $F(1) = 1$
For the homogeneous version of the recurrence, I have:
$F(n) - F(n - 1) - F(n - 2) = 0$
Finding the roots, I get:
$F(n) = α(\frac{1 + √5}{2})^n + β(\frac{1 - √5}{2})^n$
If I take the initial conditions into consideration and incorporate the non-homogeneous part, I have:
$F(0) = α(\frac{1 + √5}{2})^0 + β(\frac{1 - √5}{2})^0 - c_1(0) - c_2 = 0$
$α + β - c_2 = 0$
$α + β = c_2$
$β = c_2 - α$
$F(1) = α(\frac{1 + √5}{2})^1 + β(\frac{1 - √5}{2})^1 - c_1(1) - c_2 = 1$
$α(\frac{1 + √5}{2}) + β(\frac{1 - √5}{2}) - c_1 - c_2 = 1$
$α(\frac{1 + √5}{2}) + β(\frac{1 - √5}{2}) = 1 + c_1 + c_2$
Plugging in value of β from F(0) evaluation
$α(\frac{1 + √5}{2}) + (c_2 - α)(\frac{1 - √5}{2}) = 1 + c_1 + c_2$
$α(\frac{1 + √5}{2}) - α(\frac{1 - √5}{2}) + c_2(\frac{1 - √5}{2}) = 1 + c_1 + c_2$
$α√5 + c_2(\frac{1 - √5}{2}) = 1 + c_1 + c_2$
$α√5 = 1 + c_1 + c_2 - c_2(\frac{1 - √5}{2})$
$α = \frac{1 + c_1 + c_2 - c_2(\frac{1 - √5}{2})}{√5}$
Now that I have the values of α and β, I can plug them into the formula:
$F(n) = α(\frac{1 + √5}{2})^n + β(\frac{1 - √5}{2})^n - c_1n - c_2$
$F(n) = (\frac{1 + c_1 + c_2 - c_2(\frac{1 - √5}{2})}{√5})(\frac{1 + √5}{2})^n + (c_2 - α)(\frac{1 - √5}{2})^n - c_1n - c_2$
$F(n) = (\frac{1 + c_1 + c_2 - c_2(\frac{1 - √5}{2})}{√5})(\frac{1 + √5}{2})^n + (c_2 - \frac{1 + c_1 + c_2 - c_2(\frac{1 - √5}{2})}{√5}))(\frac{1 - √5}{2})^n - c_1n - c_2$
Now, this should be the solution to the recurrence relation, but, for example, when I use $c_1 = 2$ and $c_2 = 3$, I get the following values:
$F(2) = 2$ --> should be 8
$F(3) = 6$ --> should be 18
$F(4) = 13$ --> should be 37
$F(5) = 26$ --> should be 68
And so on ...
Could anybody tell me where I'm going wrong? Thanks
If I'm following what you've done, you've found that the general solution to the associated homogenous equations is $$\alpha\left(\frac{1+\sqrt5}2\right)^n+\beta\left(\frac{1-\sqrt5}2\right)^n$$ You have a typo when this formula first appears -- a plus sign instead of a minus sign in the second term.
That looks right. (I haven't checked it, I'm going by memory here.)
The next thing you should do is to find any particular solution to the inhomogeneous equation $$F_n-F_{n-1}-F_{n-2}=c_1n+c_2$$ Because of the form of the right hand side, we guess that there will be a solution of the form $F_n=an+b$ for some constants $a$ and $b$.
Substituting in in the inhomogeneous equation, we get $$an+b-(a(n-1)+b)-(a(n-2)+b)=c_1n +c_2$$ which, if I haven't made a mistake, leads to $$a = -c_1,\ b=-(c_2+3c_1)$$
Now the general solution to the inhomogeneous equation is the general solution to the homogeneous equation plus any particular solution to the inhomogeneous equation: $$F_n= \alpha\left(\frac{1+\sqrt5}2\right)^n+\beta\left(\frac{1-\sqrt5}2\right)^n-c_1n-c_2-3c_1$$
Now you can substitute the initial values $F_0=0,\ F_1=1$ and determine $\alpha and $\beta$. Check my calculations before you do, though.