1
$\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 '20 at 15:24
  • $\begingroup$ @jjagmath can you explain further? $\endgroup$
    – Clover
    Oct 20 '20 at 15:27
  • $\begingroup$ @Clover, I edited as jjagmath suggested. Please check I didn't change anything by mistake. $\endgroup$
    – cosmo5
    Oct 20 '20 at 15:29
  • $\begingroup$ Please, you can read the MSE-${\tt MathJax}$ Tutorial. Thanks. $\endgroup$ Oct 20 '20 at 15:30
  • 1
    $\begingroup$ @cosmo5 you accidentally removed the initial values but I added it back again $\endgroup$
    – Clover
    Oct 20 '20 at 15:36
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$
    – Clover
    Oct 20 '20 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 '20 at 16:29
0
$\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$

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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.