Determining Particular Solutions for Exponential-Polynomial Forcing Terms in Linear Nonhomogeneous Recurrence Relations

This paper develops a systematic method for determining particular solutions of the $k$th-order linear nonhomogeneous recurrence relation $$a_n+c_1{a}_{n-1}+\cdots +c_k{a}_{n-k}=\sum _{j=1}^J{p}_j(n){r_j}^n$$ with $n\ge k$, $c_k\mathrm{\ne }0$, $r_j\mathrm{\ne }0$. Here each $p_j(n)$ is a polynomial. The main result is the following: for the characteristic polynomial $c(t)=t^k+c_1{t}^{k-1}+\cdots +c_k$, if $s_j$ denotes the multiplicity of $r_j$ as a root of $c(t)$ ($s_j=0$ when $r_j$ is not a root), then there exists a particular solution of the form $q_n={\sum }_{j=1}^J{b}_j(n)n^{s_j}{r}_j^n$, where each $b_j(n)$ is a polynomial of the same degree as $p_j(n)$. This result parallels the method of undetermined coefficients for linear ODEs with constant coefficients and yields a systematic procedure for determining the form of particular solutions.