nonhomogeneous recurrence relation with $f(n)=4*n-3$

Question

I am trying to solve this recurrence relation: $a_n=a_{n-1}+4n-3$ I was trying to solve it using characteristic equation. First I found homogeneous solution:

$a_n-a_{n-1}=0$

$x=1$

$a_n=A*1^n$

And then I tried to find particular solution, but I got stucked. I tried to increase recursion level and add up the equations to get rid off the 3. And then tried to find particular solution in form of $an+b$ and substitute in recursion but I got solutions $a=0, b=0 $. I'm confused, can I even solve it using this method. Can I find some other form for finding particular solution instead of $an+b$ without increasing recursion level. If not what are some techniques I can use to find explicit solution. I wouldn't like to guess the solution and then prove it by induction.

Answer 1

Approach 1:

$$a_n-a_{n-1}=4n-3$$

$$a_{x}-a_{x-1}=4x-3$$

Sum both sides from $1$ to $n$ this should scream out to you telescoping series!

Approach 2:

$$a_n-a_{n-1}=4n-3$$

Then it's not hard to prove that if $a_n$ is a polynomial than it must be of degree $2$. Then we have :

$$c_2n^2+c_1n+c_2=a_n$$

So substitute in $3$ terms and solve the system of equations.

Approach 3

If $a_n$ is degree $2$ then $3$ terms is enough to define $a_n$. Let $a_0$ denote the first term. And $\Delta a_n$ denote $a_{n+1}-a_n$ then we have:

$$a_n : a_0,a_0+1,a_0+6,...$$

$$\Delta a_n : 1,5,...$$

$$\Delta^2 a_n : 4,...$$

And because if $a_n$ is degree $x \geq 1$, then $a_{n+1}-a_{n}$ is degree $x-1$. It follows that $\Delta^k a_n=0$ for $k \geq 3$. And noting the first terms of our sequences are $a_0,1,5,0,0,...$ and using a result from umbral calculus (if you want the proof let me know) we have:

$$a_n=a_0{n \choose 0}+1{n \choose 1}+4{n \choose 2}+0{n \choose 3}+\cdots$$

$$=a_0{n \choose 0}+1{n \choose 1}+4{n \choose 2}$$

$$=a_0+1\frac{n}{1!}+4\frac{n(n-1)}{2!}$$

$$=a_0+2n^2-n$$

Answer 2

One simple approach is to ‘unwind’ the recurrence:

$$\begin{align*} a_n&=a_{n-1}+4n-3\\ &=a_{n-2}+4(n-1)-3+4n-3\\ &=a_{n-2}+4\sum_{k=0}^1(n-k)-2\cdot3\\ &=a_{n-3}+4(n-2)-3+4\sum_{k=0}^1(n-k)-2\cdot3\\ &=a_{n-3}+4\sum_{k=0}^2(n-k)-3\cdot3\\ &\;\;\vdots\\ &=a_{n-\ell}+4\sum_{k=0}^{\ell-1}(n-k)-3\ell\\ &\;\;\vdots\\ &=a_0+4\sum_{k=0}^{n-1}(n-k)-3n\\ &=a_0+4\sum_{k=1}^nk-3n\\ &=a_0+2n(n+1)-3n\\ &=a_0+2n^2-n\;. \end{align*}$$

Since the general expression in the middle of the calculation was obtained by inspection of the pattern, technically you should then prove by induction that the final formula is correct, but it’s pretty clear that it is.

Generating functions will also work well if you’re familiar with them.

Answer 3

You can apply the principle of superposition of solutions:

• the equation $\;\Delta f=f(n)-f(n-1)= 3\;$ has solutions $\;f(n)=f(0)+3n$.
• the equation $\; n\;$ has solution $\;f(n)=f(0)+\dfrac{n(n-1)}2$.

Hence the given equation has solution $$f(n)=f(0)+ 2n(n-1)-3nf(0)+n(2n-5).$$

In case $x=1$ would mean $f(0)=1$, this yields $f(n)=2n^2-5n+1$.

Answer 4

Here's another way to solve this. Note that: $a_{n-1} = a_{n-2} + 4(n-1) - 3 = a_{n-2} + 4n - 7$. Hence:

$$a_n - a_{n-1} = a_{n-1} + 4n - 3 - a_{n-2} - 4n + 7 \implies a_n = 2a_{n-1} - a_{n-2} + 4$$

Similarly we can get rid of the $4$ and arrive at:

$$a_n - a_{n-1} = 2a_{n-1} - a_{n-2} + 4 - 2a_{n-2} + a_{n-3} - 4 \implies a_n = 3a_{n-1} - 3a_{n-2} + a_{n-3}$$

This is a simple homogenous reccurence relation and after solving it we have that:

$$a_n = (An^2 + Bn + C)(1)^n$$

Solving it for $a_0, a_1=1+a_0$ and $a_2 = 6 + a_0$ we get that:

$$\boxed{a_n = 2n^2 - n + a_0}$$