A simple recursion:
$a_{n+1} - a_n = 2n +3 , n \ge 0 , a_0 = 1 $
I can solve this by simply writing out multiple lines, and deducing that $a_n = (n+1)^2 , n \ge 0 $
However, I would like to solve this using two other methods:
- Solving for the homogeneous, solving for a particular, and combining.
- Solving using generating functions.
My attempts at both have been very unsuccessful. In particular, I would really like to learn the first method on this equation.
To solve for the homogeneous equation, remove any term that doesn't have an "a" in it: $$a_{n+1} - a_{n} = 0$$ A homogeneous recurrence relation with constant coefficients has a typical solution method. Let $a_n = C*λ^n$, where C is any constant: $$C*λ^{n+1} - C*λ^{n} = 0$$ Divide both sides by $C*λ^n$: $$λ - 1 = 0$$ $$λ = 1$$
As such, the homogeneous solution is $a_n = C*1^n = C$
Now, we want to solve for the non-homogeneous solution. We want to find the solution to: $$a_{n+1} - a_{n} = 2n + 3$$ We essentially do this by educated guessing. Since the right side is of the form An + B, we would let $a_n = An + B$. However, if you try it, you'll find it doesn't work. So, the next guess is to let $a_n = An^2 + Bn + C$: $$A(n + 1)^2 + B(n + 1) + C - An^2 - Bn - C = 2n + 3$$ $$2An + A + B = 2n + 3$$
You can set up a system of equations to equate the coefficients, but in this case it's pretty simple. $A = 1, B = 2$ Putting that back into our original guess tells us:
The non-homogeneous solution is $a_n = n^2 + 2n$
This is the easiest part. The general solution is the sum of both solutions.
The general solution is $a_n = n^2 + 2n + C$
Where C is any constant. Then, you can find your specific solution by plugging in your point and solving for C.