2
$\begingroup$

This is a nonhomogeneous recurrence relation, so there is a homogeneous and a particular solution.

Homogenous:

$a_n - 4a_{n-1} + 3a_{n-2} = 0$

$r^2 - 4r + 3 = 0$

$(r - 3)(r - 1)$

$a_n^h = \alpha(3^n) + \beta(1^n)$

This is where my solution stops because I don't know how to solve the particular solution since it would be $a_n - 4a_{n-1} + 3a_{n-2} = 2^n + n + 3$ and I'm not sure what form it should be. Would it be $A_0(r^n) + A_1(n) + A_2$ where $A_n$ is a constant or not?

I've tried solving it with that form and it ended like this:

$A_0(2^n) + A_1(n) + A_2 - 4(A_0(2^{n-1}) + A_1(n-1) + A_2) + 3(A_0(2^{n-2}) + A_1(n-2) + A_2) = 2^n + n + 3$

After simplifying and dividing $2^{n-2}$:

$A_0(2^n) - 4A_0(2^{n-1}) + 3A_0(2^{n-2}) - 4 = n + 3 + 2A_1(n) + 2A_2 - 2A_1$

And that's where I stop since I don't know what to do next.

Thanks for answering.

$\endgroup$
9
  • 1
    $\begingroup$ Use a_{n-1} to get $a_{n-1}$ $\endgroup$
    – jjagmath
    Oct 20, 2020 at 15:24
  • $\begingroup$ @jjagmath can you explain further? $\endgroup$
    – Maya
    Oct 20, 2020 at 15:27
  • $\begingroup$ @Clover, I edited as jjagmath suggested. Please check I didn't change anything by mistake. $\endgroup$
    – cosmo5
    Oct 20, 2020 at 15:29
  • $\begingroup$ Please, you can read the MSE-${\tt MathJax}$ Tutorial. Thanks. $\endgroup$ Oct 20, 2020 at 15:30
  • 1
    $\begingroup$ @cosmo5 you accidentally removed the initial values but I added it back again $\endgroup$
    – Maya
    Oct 20, 2020 at 15:36

3 Answers 3

1
$\begingroup$

So we have $$ a_{\,n} - 4a_{\,n - 1} + 3a_{\,n - 2} = 2^{\,n} + n + 3 = q(n) $$ and the solutions to the homogeneous equations are $$ 3^{\,n} ,\;1 $$

The homogeneous equation has constant coefficients and $$ q(n) = 2^{\,n} + \left( {n + 3} \right) $$ is the sum of two terms of the form $$ c^{\,n} \cdot {\rm polynomial}(n) $$

Then the theory says that in this case we can look for particular solutions of the form $$ 2^{\,n} \left( {An + B} \right),\quad C\left( {n + 3} \right)^{\,2} + D\left( {n + 3} \right) + E $$ (method of Undetermined Coefficients).

Since the constant term $E$ is already a homogeneous solution we can omit it and with simple passages we get $$ A = 0,\;B = - 4,\;C = - 1/4,\;D = - 1 $$

So the solution is $$ a_{\,n} = \alpha \,3^{\,n} + \beta - 4 \cdot 2^{\,n} - {{\left( {n + 3} \right)^{\,2} } \over 4} - \left( {n + 3} \right) $$

$\endgroup$
0
$\begingroup$

There is no point in including a constant term in the particular solution because constants are part of the solution of the homogeneous equation. Try $A_0 2^n + A_1 n^2+ A_2 n$.

This way you will conclude that the general solution is given by $$ a_n = \alpha 3^n + \beta - 2^{n+2} -\frac 14 n^2 -\frac 52 n. $$

Now you just need to compute $\alpha, \beta$ so that the initial conditions are satisfied.

$\endgroup$
2
  • $\begingroup$ Should the characteristic root then be $r^2 - 4r + 3 = 3$? And why $A_{1}n^2 + A_{2}n$ instead of $A_{1}n + A_{2}$ for the particular solution? $\endgroup$
    – Maya
    Oct 20, 2020 at 15:46
  • $\begingroup$ @Clover The characteristic polynomial is always relative to the homogeneous equation. The inicial choice for the particular solution would indeed be $A_0 2^n + A_1 n + A_0$ but, as you have seen, when you plug it into the equation you get an impossible system for computing the constants. When this happens, a common fix is to multiply by $n$. $\endgroup$ Oct 20, 2020 at 16:29
0
$\begingroup$

Here's an alternative approach. Let $A(z)=\sum_{n\ge 0} a_n z^n$ be the ordinary generating function for $a_n$. Then the recurrence relation implies that \begin{align} A(z) - a_0 - a_1 z &= \sum_{n\ge 2}\left(4a_{n-1} - 3a_{n-2} + 2^n + n + 3\right)z^n \\ &= 4z \sum_{n\ge 2} a_{n-1} z^{n-1} - 3z^2 \sum_{n\ge 2} a_{n-2} z^{n-2} + \sum_{n\ge 2} (2z)^n + z \sum_{n\ge 2} n z^{n-1} + 3\sum_{n\ge 2}z^n \\ &= 4z (A(z)-a_0)- 3z^2 A(z) + \frac{(2z)^2}{1-2z} + z\left(\frac{1}{(1-z)^2}-1\right) + \frac{3z^2}{1-z}, \end{align} so \begin{align} A(z) &= \frac{a_0 + a_1 z -4 a_0 z + \frac{4z^2}{1-2z} + \frac{z}{(1-z)^2}-z + \frac{3z^2}{1-z}}{1-4z+3z^2}\\ &= \frac{1 - z + \frac{4z^2}{1-2z} + \frac{z}{(1-z)^2} + \frac{3z^2}{1-z}}{1-4z+3z^2}\\ &= \frac{1 - 4 z + 14 z^2 - 24 z^3 + 12 z^4}{(1 - 2 z) (1 - 3 z)(1 - z)^3 } \\ &= -\frac{4}{1-2 z} + \frac{39/8}{1-3 z} + \frac{19/8}{1-z} - \frac{7/4}{(1-z)^2} - \frac{1/2}{(1-z)^3} \\ &= \sum_{n\ge 0}\left(-4\cdot 2^n + \frac{39}{8}\cdot3^n + \frac{19}{8} - \frac{7}{4}\binom{n+1}{1} - \frac{1}{2}\binom{n+2}{2}\right)z^n, \end{align} which immediately implies that \begin{align} a_n &= -4\cdot 2^n + \frac{39}{8}\cdot3^n + \frac{19}{8} - \frac{7}{4}\binom{n+1}{1} - \frac{1}{2}\binom{n+2}{2} \\ &= \frac{- 2^{n + 5} + 13\cdot 3^{n + 1} -2 n^2 - 20 n + 1}{8}. \end{align}

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .