1

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.

Tony Tarng
  • 481
  • 6
  • 18

5 Answers5

4

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$

Lance Sackless
  • 560
  • Could you elaborate why this method doesn't apply here? – Tony Tarng Jun 26 '16 at 12:43
  • As I learned it the method using roots of polynomials only applies to linear homogeneous recurrences. I.e. $x_{n+1} = a_0 x_n+a_1 x_{n-1}+\cdots+a_m x_{n-m}$. Since the term $7n$ is there, this one doesn't fit. There may be generalizations I don't know about though. – Lance Sackless Jun 26 '16 at 12:50
  • 1
    Don't be too quick to assert that a method doesn't work! See my answer for how to use it properly. =) – user21820 Jun 26 '16 at 13:00
4

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.

user21820
  • 57,693
  • 9
  • 98
  • 256
4

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.

awllower
  • 16,536
  • Note that the $(1-x)^{-3}$ in this answer corresponds to the $(D-1)^3$ in my answer, due to correspondence between $(D-1)(a)$ and $(x-1)f(x)$. – user21820 Jun 26 '16 at 13:18
  • Thanks for the explanation on this correspondence! :D – awllower Jun 26 '16 at 13:21
  • You're welcome. I prefer to use $R$ whenever possible, but generating functions can do many interesting things that cannot be expressed using $R$. And it's nice that one can put in the initial conditions straightaway in the generating function. Sorry my earlier comment should have said "$R$" not "$D$" lol.. – user21820 Jun 26 '16 at 13:26
  • To a so lazy man as me that the various methods out there for recurrence relations in existence are too complicated, using the generating functions at the first place seems to be a good habit: it can lead to solutions even if one does not know how to guess. :P – awllower Jun 26 '16 at 13:30
  • Well some things are very elegantly done with operators and not with generating functions (see the links in my profile under "Forward Difference Operator"), so I guess it's best to know both. =) – user21820 Jun 26 '16 at 13:36
  • Yes, I always admire the beauty of such operators as $R$ and the coefficient operator, or those of the same kind. :D – awllower Jun 26 '16 at 13:37
3

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}}.$$

Jack D'Aurizio
  • 353,855
1

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

Robert Israel
  • 448,999
  • Could you explain it a bit more? How can you tell $An + B$ won't work? – Tony Tarng Jun 26 '16 at 12:48
  • @TonyTarng: See my answer for why your reasoning is incorrect and how one can know to try a quadratic. It also explains Robert's remark in the following sense: Since the original homogenous part of the recurrence is $(R-1)(a) = 0$, we know that when we have a polynomial in the non-homogenous part, we need to apply $(R-1)$ to both sides repeatedly to vanish it, and recall that if you have $(R-c)^k$ in the characteristic part then the corresponding term in the general solution is $P(n) c^n$ where $P$ has degree $k-1$. So both homogenous and non-homogenous parts contribute to the characteristic. – user21820 Jun 26 '16 at 13:13