I was interested in Solution of this Non-Homogenous Recurrence Relation
$f(n)=f(n-1) + f(n-3) + 1$
The Base conditions are:
$f(0)=1$
$f(1)=2$
$f(2)=3$
Since, the equation is non-homogenous, it will consists of Two Parts.
- Finding solution of
Associated Homogenous Recurrence Relation f(n)=f(n-1)+f(n-3)
For this the characteristic equation will be $x^3-x^2-1=0$
Ideally, 3 roots should be there contributing to Solution Terms, but I am able to find only one real root. Thus, unable to find solution of Associated Homogenous Recurrence Relation. - Finding
Particular Solution
It was difficult to calculate, therefore, Using this Online Calculators, one can find answer by inputting
f(n)=f(n-1)+f(n-3)+1, f(0)=1, f(1)=2, f(2)=3
The solution is quite complex. Thus, I was interested if we can deduce that
$f(n) \geq x^n$ for some $x\epsilon \mathbb{R} $
Please help.
First all all, let $f_n=g_n-1$ to make $$g_n=g_{n-1}+g_{n-3} \qquad \text{with} \quad g_0=2,g_1=3,g_2=4$$ The real solution of $r^3=r^2+1$ is given by $$r_1=\frac{1}{3} \left(1+2 \cosh \left(\frac{1}{3} \cosh ^{-1}\left(\frac{29}{2}\right)\right)\right)$$ Write $$r^3-r^2-1=(r-r_1)(r^2+a r+b)$$ to get $$a=\frac{2}{3} \left(\cosh \left(\frac{1}{3} \cosh ^{-1}\left(\frac{29}{2}\right)\right)-1\right) \quad\text{and} \quad b=\frac{3}{1+2 \cosh \left(\frac{1}{3} \cosh ^{-1}\left(\frac{29}{2}\right)\right)}$$ So, solving the quadratic $r^2+ar+b=0$, you have the complex roots $r_2$ and $r_3$.
Now, use the conditions to get $(c_1,c_2,c_3)$ and I suppose that this will again involve a cubic equation with only one real root to generate real value of $g_n$ and $f_n$.
It could probably be easier to identify the generating function which is not very complex.
In view of the numbers $f(n) > \big[\sqrt 2\big]^n$