Solving $a_n = a_{n-1} + 7n$ for $n\ge1$ and $a_0 = 4$

Question

First, I found the homogeneous solution: $$r^n - r^{n-1} = 0$$ $$\Rightarrow r = 1$$ So the homogeneous solution is of the form: $$c(1)^n = c$$ Then, to find a particular solution, I "guessed" the form $An+B$, then plug it into the equation: $$An+B = A(n-1)+B+7n$$$$\Rightarrow A = 7n$$ So I assumed the solution would be $c + 7n^2$, then plugging in $a_0 = 4$ gives c =4, so the final solution (incorrect) is $$4 + 7n^2$$

But after comparing with some values, the solution is obviously wrong.

I recently started learning how to solve these linear recurrence relations, and it's really confusing, so hopefully someone can tell me what I'm doing wrong here.

Answer 1

Let $R$ be the right-shift operator:

$R = ( f \mapsto ( n \mapsto f(n+1) ) )$.

Then your equation is:

$(R-1)(a) = ( n \mapsto 7n )$.

Apply $(R-1)$ to both sides repeatedly until the right-hand side vanishes!

$(R-1)^2 (R-1)(a) = ( n \mapsto 0 )$.

Now we can use the general solution for homogenous linear recurrence relations:

$a = ( n \mapsto (pn^2+qn+r) 1^n )$ for some $p,q,r$.

Note that if the right-hand side had a term of the form $n^k c^n$, apply $(D-c)$ to both sides repeatedly and it will vanish.

As for why your attempt is invalid, it is because you made a logical error; if you guess that $a_n = An+B$ for some constant $A,B$, and you get $A = 7n$, which is not a constant, it implies that your guess is wrong. If you guessed $a_n$ is a quadratic in $n$, you would be able to solve for the coefficients. Why you need a quadratic in general is explained completely by the above solution.

Answer 2

That method doesn't apply to this type of recurrence.

For this one, it's probably simplest to work out the first few terms and guess the pattern.

\begin{align*} a_0 &= 4\\ a_1 &= 4+7\cdot 1\\ a_2 &= 4+7\cdot 1+7\cdot 2\\ a_3 &= 4+7\cdot 1+7\cdot 2 + 7\cdot 3\\ \ldots \end{align*}

So $a_n = 4+7(1+2+\cdots+n) = 4+7n(n+1)/2$

Answer 3

Your form for the particular solution is wrong, because it contains the solution of the homogeneous equation ($B$). Try $An + B n^2$.

Answer 4

Given $$ a_{n}-a_{n-1} = 7n $$ it follows that: $$ a_N-a_0=\sum_{n=1}^{N}(a_{n}-a_{n-1})=\sum_{n=1}^{N}7n = 7\cdot\frac{N(N+1)}{2}$$ so: $$ a_N = \color{red}{4+\frac{7N(N+1)}{2}}.$$

Answer 5

If the generating function is allowed, then this can be solved as follows:
Define $$\color{blue}{f(x):=\sum\limits_{n=0}^\infty a_nx^n}.$$
Then from the recurrence relation, we have:
$$a_nx^n=a_{n-1}x^n+7nx^n.$$
Summing over $n,$ we have $f(x)-a_0=xf(x)+7\sum\limits_{n=1}^\infty nx^n.$ Since $$\sum\limits_{n=1}^\infty nx^n=x\dfrac{d(1/(1-x))}{dx}=\dfrac{x}{(1-x)^2},$$ we conclude that $$\color{red}{f(x)=\frac{1}{(1-x)}(4+\frac{7x}{(1-x)^2})}.$$
Expanding it out, either by differentiating twice the series $\sum\limits_{n=0}^\infty x^n,$ or by binomial theorem applied to $(1-x)^{-3},$ we obtain : $$a_n=4+\frac{7n(n+1)}{2}.$$

Hope this helps.