I'm struggling hard with figuring out how to solve the following inhomogeneous equation: $$a_n=a_{n-1}+3(n-1), a_0=1$$
My work is as follows:
I solve for the homogeneous portion, which is $a_n = 1^n$, then solve for $$a^*_n = B_1n+B_0 = a^*_{n-1}+B_0+3n$$ $$a^*_n = B_1n+B_0 = B_1(n-1)+B_0+3n$$ but after seperating by constant and n-term, I end up getting a system of equations that doesn't evaluate for any of the $B$ variables. Guidance in the right direction and some material to read would be excellent.
The other answers aside, I will show you a powerful (i.e. widely applicable) method of solving such questions, known as generating functions.
First, we define our generating function. Let $F(x)=\sum_{n=0}^{\infty}a_nx^n$ be our generating function for this recurrence. Note that despite the function involving $x$, this is not to be thought of as an actual function of $x$; that is, we will not be substituting any numerical values for $x$, nor are we performing a summation. The role of the powers of $x$ is simply to be "labels" for the coefficients, which are precisely the terms of the sequence generated by the recurrence. The summation is simply an algebraic convenience; it is meant to represent all infinitely-many terms of the sequence at once. Our goal is to find a (hopefully) closed-form formula for these coefficients.
To begin the method, multiply each term in the recurrence by $x^n$ and sum over all values of $n$ for which the recurrence is valid, i.e. for all $n\geq 1$:
$$\sum_{n=1}^{\infty}a_nx^n = \sum_{n=1}^{\infty}a_{n-1}x^n+3\sum_{n=1}^{\infty}nx^n-3\sum_{n=1}^{\infty}x^n$$
Now we examine each term and attempt to relate them algebraically to $F(x)$. To do so, it will be helpful to expand the first few terms of each series. Beginning with $F(x)$, we see that:
$$F(x)=a_0+a_1x+a_2x^2+a_3x^3+a_4x^4+...$$
While the first few terms of the series on the LHS of our equation are:
$$\sum_{n=1}^{\infty}a_nx^n=a_1x+a_2x^2+a_3x^3+a_4x^4...$$
The relation here is pretty clear: $\sum_{n=1}^{\infty}a_nx^n$ is equal to $F(x)-a_0$. Moving right along, the expansion of the first series on the RHS is:
$$\sum_{n=1}^{\infty}a_{n-1}x^n= a_0x+a_1x^2+a_2x^3+a_3x^4+a_4x^5+...$$
Again, the relationship is pretty clear. This is simply equal to $xF(x)$. Now for the second term on the right:
$$3\sum_{n=1}^{\infty}nx^n=1x+2x^2+3x^3+4x^4+...$$
Although not as simple as the first two series, this is still pretty easy to handle. First, take a look at the following series:
$$\sum_{n=0}^{\infty}x^n=1+x+x^2+x^3+x^4+...$$
Now look at what happens if we differentiate this term-by-term with respect to $x$:
$$\frac{d}{dx}\sum_{n=0}^{\infty}x^n=1+2x+3x^2+4x^3+5x^4...$$
The first series, $\sum_{n=0}^{\infty}x^n$, is known as the geometric series; it has a closed form of $\frac{1}{1-x}$. The second series is the derivative of this; as such, it has the closed form $\frac{1}{(1-x)^2}$. It is not quite equal to the series we want; however, if we multiply through by $x$, it will be exactly equal. Together with the coefficient of $3$, the final closed form of $\sum_{n=1}^{\infty}nx^n$ is $\frac{3x}{(1-x)^2}$.
The final term, $\sum_{n=1}^{\infty}x^n$, is perhaps the simplest of all. Its expansion is as follows:
$$\sum_{n=1}^{\infty}x^n=x+x^2+x^3+x^4+x^5+...$$
We see that this is nothing but the geometric series multiplied by $x$. We know the closed form for the geometric series is $\frac{1}{1-x}$; multiplying through by $-3x$, we get that the closed form of $\sum_{n=1}^{\infty}x^n$ is $\frac{-3x}{1-x}$.
Now to put it all together. Substituting the closed form for each series in our equation, we arrive at the following:
$$F(x)-a_0=xF(x)+\frac{3x}{(1-x)^2}-\frac{3x}{1-x}$$
Solving for $F(x)$ and substituting $1$ for $a_0$ yields:
$$F(x)=\frac{1}{1-x}+\frac{3x}{(1-x)^3}-\frac{3x}{(1-x)^2}$$
Now what? What we have done is to construct a rational representation of $F(x)$; as mentioned in the beginning, the utility of this is that should the expression on the right be expanded as a series, the coefficient of $x^n$ will be equal to $a_n$, _for all $n$!
"That's all well and good", you might be thinking, "but how do we actually get the coefficients we want? Wouldn't it be a lot of work to expand it as a series?"
Great question. It is true that expanding this expression would be a lot of work; in fact, probably more work than simply computing the recurrence the normal way. However, there is a shortcut we can use: the extended binomial theorem.
Extended binomial theorem: given a rational expression of the form $\frac{ax^s}{(1-x)^n}$, the coefficient of $x^k$ in its expansion — denoted $[x^k]$ — is equal to $a\binom{n+k-s-1}{k-s}$. Furthermore, given multiple terms of this type, the overall value of $[x^k]$ is equal to the sum of the value of $[x^k]$ for each term.
Let's now apply that to our problem:
$$[x^k](\frac{1}{1-x}+\frac{3x}{(1-x)^3}-\frac{3x}{(1-x)^2})=[x^k]\frac{1}{1-x}+[x^k]\frac{3x}{(1-x)^3}-[x^k]\frac{1}{(1-x)^2}$$ $\Longrightarrow$ $$[x^k]=\binom{k}{k}+3\binom{k+1}{k-1}-3\binom{k}{k-1}$$
There are simple forms for each of these terms. Substituting them for what we have yields:
$$[x^k]=1+3\frac{k(k+1)}{2}-3k=1+\frac{3k(k-1)}{2}$$
Now remember, the $n^{th}$ term of the sequence generated by the recurrence is equal to the coefficient of $x^n$ in the expansion of our series equation, and we denote it by $[x^n]$. Replacing $[x^k]$ with $a_n$ and all instances of $k$ with $n$ yields the final solution:
$$a_n=1+\frac{3n(n-1)}{2}$$
Closing notes: the absolute number one resource for learning about generating functions is (in my opinion) generatingfunctionology by Herbert Wilf. It is freely available for download and I can't recommend it enough.
Second, is it worth learning about generating functions given this sort of problem? In my opinion, the answer is an emphatic "yes". While it's true that this technique was overkill for this problem, there's really no limit on the recurrences that it can handle, and you don't even need to concern yourself with homogeneity! You won't always get such a nice closed form for the recurrence using generating functions, but it's unlikely in the extreme that any other technique will give you one, so you lose nothing. Generating functions are used in a vast range of mathematical fields: linear recurrence relations (and by extension, differential and difference equations, which involve combinatorics, linear algebra and dynamical systems), moment generating functions (probability and statistics), number theory, analysis, and so much more. The takeaway: it's definitely better to know them and not need them than it is to need them and not know them, because the chances of never needing them are slim at best!