Understanding what a particular solution of a recurrence relation is?

Question

What does the particular solution of a linear nonhomogeneous recurrence relation actually mean? To me it looks that the particular solution looks exactly like the original given recurrence relation. Shouldn't then the particular part also have a homogeneous part and it's own particular part? Or is the particular solution just a value (expressed in a modified form of the given function) for which the linear nonhomogeneous recurrence relation holds? I am really confused and actually stuck in this one for a while now.

Answer 1

Since this is a principle that occurs multiple times, I'll try to give you some intuition that helped me. But first to directly answer your question:

1. The particular solution is a concrete sequence of numbers that satisfies the recurrence relation (but not necessarily the initial conditions you were given). You choose whichever you happen to find.
2. Both the particular solution that you were able to find (say, by guessing) and the one you are looking for (which is also "particular", i.e. it is a specific sequence that satisfies the relation) reside in the same set of all solutions, they just have different initial conditions but one is not more special than the other.
3. Once you fix some sequence $a_n$ as your preferred particular solution, it also has a homogeneous part: it's just zero ($a_n = 0 + a_n$, as $0$ is always in the set of homogeneous solutions). If you picked another particular solution $b_n$, and wrote $a_n$ in terms of $b_n$ (that is, $a_n = b_n + c_n$), then you could say that the solution $a_n$ "has a nontrivial homogeneous part" $c_n$. You pick the particular solution as a starting point and look at all other solutions relative to it.
4. The homogeneous part, however, is always a member of the space of solutions for the corresponding homogeneous recurrence, which is usually easy to determine. If the initial linear recurrence isn't homogeneous, then this part by itself is not a solution to it, it only becomes one if you add a particular solution to it.

In short, adding a homogeneous solution to a general solution does not make you jump out of the set of general solutions. In fact you can generate all solutions that way, as if you had a basis.

For me the best intuition on the principle "general solution = solution to homogeneous + one particular solution" comes from linear algebra (for simplicity all in $\mathbb{R}^n$ and $\mathbb{R}^{n \times n}$). Suppose you have a system of linear equations $Ax = b$, and one particular solution $x^p = (x_1 \cdots x_n) \in \mathbb{R}^n$ for which $Ax^p = b$.

One can solve the corresponding homogeneous system $Ax = 0$, and the solution set $H$ is always a subspace of $\mathbb{R}^n$ (the nullspace of $A$). If $A$ is of full rank, then $\dim(H) = 0$ i.e. $x = 0$ is the only solution of the homogeneous equation. Nevertheless for this intuition it's best to consider cases where $H$ is a proper subspace, i.e. is of dimension at least $1$.

Back to the original nonhomogeneous equation:

$$Ax = b$$ $$Ax^p = b$$ $$A(x - x^p) = 0$$

Therefore $x - x^p \in H$, i.e. the difference of any two solutions for $Ax=b$ is a solution for $Ax=0$, because $A$ is a linear operator. We also have $A(x^h + x^p) = Ax^h + Ax^p = 0 + b = b$ for all $x^h \in H$, i.e. the previous claim that we can add arbitrary homogeneous solutions to general solutions and get general solutions as a result. More intuitively let $X$ denote the solutions set for $Ax=b$, then $X = x^p + H = \{x^p + x^h : x^h \in H\}$. This shows that solutions of the homogeneous equation are in bijection with the solutions you're interested in, and the bijection is $x^h \mapsto x^h + x^p$.

It is important that $H$ is a vector space because then you can find a basis for it, which will allow you to write the solutions in $X$ in its terms. More concretely, you will be able to express any solution to $Ax=b$ as $x = x^p + \alpha_1 u_1 + \cdots + \alpha_n u_n$ where $\{u_1, \ldots, u_n\}$ is a basis of $H$ and $\alpha_1, \ldots, \alpha_n \in \mathbb{R}$ are scalars determining some particular solution (for the particular solution $x^p$ all $0$ obviously).

The scalar coefficients $\alpha_i$ are very interesting when you carry over this principle into differential equations or recurrence relations. They are exactly what the initial conditions are supposed to constrain. That's where this shared method comes from:

1. find a particular solution (a concrete function which satisfies the differential equation or the recurrence relation irrespective of initial conditions, this part is new)
2. determine the basis for the homogeneous solution space (which is often a set of exponential functions as opposed to just elements of $\mathbb{R}^n$)
3. all that is left are the scalars, that's where you use the given initial conditions

To illustrate why this carries over to recurrence relations, consider the solutions for a linear homogeneous recurrence, say $A \cdot t_n + B \cdot t_{n-1} = 0$ (where $A, B \in \mathbb{R}$). They form a vector space where the zero element is $t_n = 0$ for all $n$. Now suppose you have a nonhomogeneous recurrence $A \cdot t_n + B \cdot t_{n-1} = f(n)$. For two sequences $u_n$ and $v_n$ that satisfy the recurrence, consider which recurrence might be satisfied by their difference $u_0 - v_0, u_1 - v_1, \ldots$. It's the corresponding homogeneous recurrence $A \cdot t_n + B \cdot t_{n-1} = 0$:

\begin{align} A \cdot (u_n - v_n) + B \cdot (u_{n-1} - v_{n-1}) &= A \cdot u_n - A \cdot v_n + B \cdot u_{n-1} - B \cdot v_{n-1}\\ &= (A \cdot u_n - B \cdot u_{n-1}) + (A \cdot v_n + B \cdot v_{n-1})\\ &= f(n) - f(n)\\ &= 0 \end{align}

Therefore, if you find one solution $t^p_n$, and solve the corresponding homogeneous recurrence, you are able to express any solution $t_n$ as $t_n = t^h_n + t^p_n$ where $t^h_n$ is from the homogeneous solution space. Not being able to do that would mean that there is no such $t_h = t_n - t^p_n$, which the above reasoning shows must exist.

Answer 2

With linear recurrences, or linear differential equations, the general solution of an inhomogeneous equation is an affine space, usually described as a "particular" solution (i.e. any solution you can find) plus solutions to the homogeneous equation. If $L$ is linear and $L(f_1)=L(f_2)=g$, then $L(f_1-f_2)=0$, i.e. the differences of any two solutions to the inhomogeneous problem is a solution to the homogeneous problem.

For instance $$ y''=2^x $$ has a particular solution $y=2^x/(\ln 2)^2$, the solutions to the homogeneous problem $y''=0$ are $y=ax+b$, and every solution is of the form $2^x/(\ln 2)^2+ax+b$ for some $a$, $b$.

Or a recurrence example: $$ a_n+2a_{n-1}=2^n $$ has a particular solution $a_n=2^{n-1}$, the solutions to $a_n+a_{n-1}=0$ are $c(-1)^n$ and every solution is of the form $2^{n-1}+c(-1)^n$.