3

How to solve this recurrence relation?

$a_{n} = a_{n-1}+a_{n-2}+n,a_{1}=a_{0}=1$

What I have tried:

$r^2 = r + 1 \rightarrow r = \frac{1+\sqrt{5}}{2},\frac{1-\sqrt{5}}{2}$

non-homogeneous part:

$$ \begin{split} a_{n} &= cn+b \implies c(n)+b = c(n-1) + b + c(n-2) + b + n\\ 0 &= -3c+b+n(c+1) \implies c+1 = 0 \iff c=-1 \implies b = -4 \\ a_{n} &= c_{0} \left(\frac{1+\sqrt{5}}{2}\right)^n + c_{1} \left(\frac{1-\sqrt{5}}{2}\right)^n -n-4 \end{split} $$

putting $a_{0}$ and $a_{1}$ in recurrence relation gives $c_{0} = (\frac{1}{2})(5+\frac{7}{\sqrt{5}})$ and $c_{1} = (\frac{1}{2})(5-\frac{7}{\sqrt{5}})$.

I am sure my answer is wrong because for n greater than 1 it doesn't work. help me correct my mistake, please.

gt6989b
  • 54,422
gigili
  • 41
  • there is no typo. what part doesn't make sense? – gigili Jul 07 '21 at 12:22
  • what a dumb mistake should i delete my question? – gigili Jul 07 '21 at 12:26
  • 1
    no, leave it. it is a good illustration of how to solve these things if someone needs a reference – gt6989b Jul 07 '21 at 12:27
  • 1
    Note : In general, to locate particular solutions of a recurrence relation with a non-linear term, you may use various ansatz and see which works. For a recurrence relation like this, if you try the function $a_n = cn+d$ then $cn+d = c(n-1)+d + c(n-2)+d + n = n(2c+1) + (2d-3)$, so we get $c = -1$ and $d=3$. Thus, a particular solution of the recurrence is $b_n = -n+3$. But now, $a_n -b_n = c_n$ satisfies the recurrence $c_n = c_{n-1} + c_{n-2}$, and now you are in good shape because you can find $c_n$ using the usual tricks (or it's the Fibonacci translated, so you know the answer). Finish. – Sarvesh Ravichandran Iyer Jul 07 '21 at 12:27
  • Alt. hint: write it as $,\left(a_n+n+3\right) = \left(a_{n-1}+(n-1)+3\right) + \left(a_{n-2}+(n-2)+3\right),$, so $,a_n+n+3,$ is a Fibonacci sequence. – dxiv Jul 07 '21 at 17:54

2 Answers2

3

the last equation $$ 0 = n(c+1) + (b-3c), $$ which implies $c+1 = 0 \iff c=-1$ and $b = 3c = -3 \ne -4$.

gt6989b
  • 54,422
2

Here's another possible approach using generating functions (a standard approach for many linear recurrences): Let us define $A(x)=\sum_{n=0}^{\infty} a_n x^n$ Then, we have: $$a_n x^n=a_{n-1} x^n+a_{n-2} x^n+n x^n$$ Summing: $$A(x)-x-1=x(A(x)-1)+x^2 A(x)+x\frac {d(\sum_{n=1}^{\infty} x^{n})}{dx}$$ Thus, we get: $$A(x)=\frac { \frac {x}{(1-x)^2}+1}{1-x-x^2}$$ The coefficient of $x^n$ in this polynomial gives $a_n$. That can now be found out using partial fractions.

Ritam_Dasgupta
  • 5,992
  • 2
  • 8
  • 23