-1

When determining the form of the particular solution for a recurrence relation is quiet simple, I use the following table:

$f(n)$ $a^p_n$
c c
$n$ $cn+d$
$n^2$ $cn^2+dn+e$
$r^n$ $cr^n$

These generally work for most of my problems but how about when there is a mixture of equations like:

$F(n) = n^22^n$, $F(n) = n^3(-2)^n$, or $F(n) = n2^n$ How can I guess the form of the particular solution in these cases?

Leuel Asfaw
  • 109

1 Answers1

1

I presume these are linear recurrences with constant coefficients. It's similar to linear constant-coefficient differential equations. If $f(n) = n^k r^n$ where $k$ is a positive integer, you might try $a_n = p(n) r^n$ where $p(n)$ is a polynomial of degree $k$. If $r^n$ is a solution of the homogeneous recurrence relation, the polynomial should have degree $k+1$ but no constant term. If $n r^n$ is also a solution of the homogeneous recurrence relation, it should have degree $k+2$ but no constant or $n^1$ term. And so on...

Robert Israel
  • 448,999
  • Or you could convert the recurrence to a differential equation by passing to the exponential generating function, and then use Undetermined Coefficients or Variation of Parameters to find a particular solution for the differential equation. – bof Dec 23 '22 at 05:40