First let me state that I am not asking about the usual procedure for finding a trial solution to a non-homogeneous recurrence. I have been doing this for many years and can solve all the basic types, but I am looking for some deeper insight.
Here are a few examples to serve as a basis for the discussion.
-
For $a_n-a_{n-1}-6a_{n-2}=n^2$ we guess $a_n=cn^2+dn+e$. Why not just $cn^2$? If you want to say "because $(n-1)^2$ contains lower order terms" please read the rest of the question before posting that answer.
-
For $a_n-a_{n-1}-6a_{n-2}=2^n$ we guess $a_n=c2^n$: no further terms as in the previous example.
-
For $a_n-a_{n-1}-6a_{n-2}=3^n$ we guess $a_n=cn3^n$. Why not just $c3^n$? (And again, I do not want the answer "because $3^n$ satisfies the homogeneous recurrence", I know that already.) Why is it not necessary to include a term $dn^23^n$?
-
For $a_n-a_{n-1}-6a_{n-2}=2^n+3^n$ we guess $a_n=c2^n+dn3^n$. How do we really know that $c2^n$ is OK but $d3^n$ is not?
-
For $a_n-6a_{n-1}+9a_{n-2}=n3^n$ we guess $a_n=cn^33^n+dn^23^n$. As above, how do we know in advance that we will not need a term $en^43^n$?
My thoughts on this are very vague, any insight (perhaps even proofs) would be greatly appreciated.
I feel that the answer must have something to do with linear independence in the vector space $V$ of all (let's say real) sequences $\{a_0,a_1,\ldots\}$.
In case 5, for example, if we start with the homogeneous solutions, we have to continue the set
$$\{3^n,\,n3^n,\ldots\}$$
until we get four independent sequences – but why four?
In case 4, I assume that we treat the two summands separately because the sequences $\{2^n\}$ and $\{3^n\}$ are linearly independent.
On the other hand, $\{n\}$ and $\{n^2\}$ are also linearly independent and this would be different. For this reason, and also to account for example 1, I suspect that we also need to consider the finite difference operator
$$S:\{a_0,a_1,\ldots\}\mapsto\{a_1-a_0,a_2-a_1,\ldots\}\ ,$$
which is a linear transformation on $V$, and perhaps to consider whether $a_n,\,S(a_n),\,S^2(a_n),\ldots$ are linearly independent.
What I would like to see is a theorem of the following shape.
If the $k$th order linear recurrence with constant coefficients
$$a_n+\cdots+c_ka_{n-k}=0$$
has solutions ${\rm span}({\bf h}_1,\ldots,{\bf h}_k)$, then the recurrence
$$a_n+\cdots+c_ka_{n-k}=f(n)$$
has solutions of the form $a_n={}????$
Any ideas will be read with interest! – but once again, please do not tell me how to solve recurrences! I know how, I am trying to understand why.
Best Answer
My suggestion is to think of the undetermined coefficient method for linear non-homogeneous ODE, which can be found in any elementary ODE book. Let me illustrate. Let say we want to find a particular solution of $$ ay''+by'+cy=f(x), $$ where $a,b,c$ are constants. If $f(x)=x^3$, you will need to plug in a polynomial of degree 3 (try it and see why you need the lower degree terms). Now, if $f(x)=e^{ax}$, then you will need to plug in $y=Ke^{ax}$. I believe it is obvious that you do not need any other terms. Notice that if $f(x)=2^x$, it is a particular case of an exponential since $f(x)=2^x=e^{\ln{(2)} x}$. Now, the only exceptions to those rules if if $f(x)$ is a solution to the homogeneous problem. For example in the case of $$ y''-y=e^x. $$ In this case, $y=ke^x$ does not work. You need to pre-multiply by $x$ to try $y=kxe^x$. In general, if $f(x)$ is a solution of the homogeneous problem, you need to pre-multiply the ansatz's I suggested above by $x$. All these results are formulated in theorems in any decent elementary ODE book (for example, the one written by Nagle and Saff). But I think these rules can be understood quite easily by working out simple examples. Note that in relation to your example $n3^n$, I can add the rule that if $f(x)=x^2 e^{ax}$ and that $e^{ax}$ is not a solution of the homogeneous problem, you need to try a polynomial of degree $3$ times $e^{ax}$. Note that if you try to add a term like $x^4e^{ax}$ to your solution, then this term will automatically produce a term proportional to $x^4e^{ax}$, which is unwanted.
If $e^{ax}$ was a solution, then you would need to pre-multiply by $x$. You would try $y=x(bx^3+cx^2+dx+f)e^{ax}$. Again, all this are in the theorems. Now, if $a$ was a double root of the characteristic equation, you would need to pre-multiply by $x^2$ instead. For example $$ y''-6y'+9y=x^2e^{3x}. $$ You would try $y=x^2(ax^2+bx+c)e^{3x}. $
Note that in the case of $n3^n$ you mention, the characteristic polynomial has a double root $3$, thus the homogeneous problem has $3^n$ and $n3^n$ as solutions, that is why you need to pre-multiply by $n^2$ and try $n^2(an+b)3^n$,
All what I said I believe extends to your difference equations. Your difference equations are ``like'' second order differential equation with inhomogeneities made of exponentials and polynomials. So, the rules for the undetermined coefficient method do extend.