Thread: Removing recursion from sequence

I think this is the right section since sequences belong to discrete math. Anyway, I have this sequence and I need to know if there is any way to remove the recursion from it:

$\displaystyle {a}_{1} = 1 $
$\displaystyle {a}_{n} = 2 * {a}_{n-1} + 3*n$

I tried to somehow turn it into exponential function but I don't know how, then I thought about moving something to the other side but I don't think it would work either. Is it even possible to write it without recursion?

The characteristic equation of $\displaystyle a_n-2a_{n-1}=0$ is $\displaystyle \lambda-2=0$ so, its solutions are $\displaystyle a_n=C2^n$ . A particular solution of the complete has the form $\displaystyle An+B$ ... etc .

Hello, Bivalgo!

$\displaystyle a_1 \:=\:1,\;\;a_n \:=\: 2a_{n-1} + 3n$

We have: .$\displaystyle a_1 = 1,\;a_2 = 8,\;a_3 = 25,\;a_4 = 62\;\hdots$

$\displaystyle \begin{array}{cccccccc}\text{We are given:} & a_n &=& 2a_{n-1} + 3n & [1] \\ \text{Next equation:} & a_{n+1} &=& 2a_n + 3(n\!+\!1) & [2] \end{array}$

$\displaystyle \text{Subtract [2] - [1]: }\:a_{n+1} - a_n \;=\;2a_n - 2a_{n-1} + 3 $

$\displaystyle \begin{array}{cccccccc}\text{And we have:} & a_{n+1} - 3a_n + 2a_{n-1} + 3 &=& 0 & [3] \\ \text{Next equation:} & a_{n+2} - 3a_{n+1} + 2a_n + 3 &=& 0 & [4] \end{array}$

$\displaystyle \text{Subtract [4] - [3]: }\;a_{n+2} - 4a_{n+1} + 5a_n - 2a_{n-1} \;=\;0 $

$\displaystyle \text{Let }X^n = a_n\!:\;\;X^{n+2} - 4X^{n_1} + 5X^n - 2X^{n-1} \;=\;0$

$\displaystyle \text{Divide by }X^{n-1}\!:\;\;X^3 - 4X^2 + 5X - 2 \;=\;0$

$\displaystyle \text{Factor: }\;(X - 1)(X - 1)(X - 2) \:=\:0 \quad\Rightarrow\quad X \:=\:1,\:1,\:2$

$\displaystyle \text{The formula is: }\;f(n) \;=\;A(1^n) + Bn(1^n) + C(2^n)$


$\displaystyle \text{Use the first three terms of the sequence to create a system of equations.}$

. . $\displaystyle \begin{array}{cccccccc} f(1) = 1\!: & A + B + 2C &=& 1 & [5] \\ f(2) = 8\!: & A + 2B + 4C &=& 8 & [6] \\ f(3) = 25\!: & A + 3B + 8C &=& 25 & [7] \end{array}$

$\displaystyle \begin{array}{cccccccc}\text{Subtract [6] - [5]:} & B + 2C &=& 7 & [8] \\ \text{Subtract [7] - [6]:} & B + 4C &=& 17 & [9] \end{array}$

$\displaystyle \text{Subtract [9] - [8]: }\;2C \:=\:10 \quad\Rightarrow\quad C \:=\:5$

$\displaystyle \text{Substitute into [8]: }\;B + 2(5) \:=\:7 \quad\Rightarrow\quad B \:=\:\text{-}3$

$\displaystyle \text{Substitute into [5]: }\:A - 3 + 10 \:=\:1 \quad\Rightarrow\qud A \:=\:\text{-}6$


$\displaystyle \text{Therefore: }\;f(n) \;=\;-6 - 3n + 5(2^n) \;=\;5\!\cdot\!2^n - 3(n+2) $

Originally Posted by Bivalgo

I think this is the right section since sequences belong to discrete math. Anyway, I have this sequence and I need to know if there is any way to remove the recursion from it:

$\displaystyle {a}_{1} = 1 $
$\displaystyle {a}_{n} = 2 * {a}_{n-1} + 3*n$

I tried to somehow turn it into exponential function but I don't know how, then I thought about moving something to the other side but I don't think it would work either. Is it even possible to write it without recursion?

Alternative solution via generating functions. (A try)

First let us define $\displaystyle {a}_{0} = 0 $.

Let $\displaystyle f(x)$ be generating function of $\displaystyle {a}_{n} $.

So:

$\displaystyle f(x)=\sum_{i = 0}^\infty a_ix^i=x+\sum_{i = 2}^\infty a_{i}x^i=x+\sum_{i = 2}^\infty (2a_{i-1}+3i}x^i)=x+\sum_{i = 2}^\infty 2a_{i-1}+\sum_{i = 2}^\infty 3ix^i=x+2x\sum_{i = 1}^\infty a_ix^i+3x\sum_{i = 2}^\infty ix^{i-1}$

Or:

$\displaystyle f(x)=x+2xf(x)+3x(\frac{1}{(1-x)^2}-1}$

Hence, $\displaystyle f(x)=\frac{3x}{(1-x)^3}-\frac{2x}{1-x}$

Or:

$\displaystyle f(x)=3x(1+x+x^2+...)^3-2x(1+x+x^2+...)$

Now, if we find the coefficient of $\displaystyle x^n$.

I found that $\displaystyle a_n=\frac{3}{2}n(n+1)-2$

But this is a wrong answer!

Where is my mistake?
Thank you.

Thank you so much for your help!

However, there are still few lines that I don't quite understand and I'd appreciate a little further explanation because I'm not really this good with math...

$\displaystyle \begin{array}{cccccccc}\text{We are given:} & a_n &=& 2a_{n-1} + 3n & [1] \\ \text{Next equation:} & a_{n+1} &=& 2a_n + 3(n\!+\!1) & [2] \end{array}$

$\displaystyle \text{Subtract [2] - [1]: }\:a_{n+1} - a_n \;=\;2a_n - 2a_{n-1} + 3 $

I know that here we calculate the difference between any two neighbouring elements of the sequence...

$\displaystyle \begin{array}{cccccccc}\text{And we have:} & a_{n+1} - 3a_n + 2a_{n-1} + 3 &=& 0 & [3] \\ \text{Next equation:} & a_{n+2} - 3a_{n+1} + 2a_n + 3 &=& 0 & [4] \end{array}$

$\displaystyle \text{Subtract [4] - [3]: }\;a_{n+2} - 4a_{n+1} + 5a_n - 2a_{n-1} \;=\;0 $

Now me move everything to the left, create second equation with incremented variable and substract the left sides to get another equation...

$\displaystyle \text{Let }X^n = a_n\!:\;\;X^{n+2} - 4X^{n_1} + 5X^n - 2X^{n-1} \;=\;0$

Here's the first thing I don't get - why do we turn n-th element of the sequence into n-th power of X?

$\displaystyle \text{Divide by }X^{n-1}\!:\;\;X^3 - 4X^2 + 5X - 2 \;=\;0$

I understand that here we divide every element by X^(n-1) to simplify the equation as much as possible...

$\displaystyle \text{Factor: }\;(X - 1)(X - 1)(X - 2) \:=\:0 \quad\Rightarrow\quad X \:=\:1,\:1,\:2$

Now we figure out the three possible values of X in this equation...

$\displaystyle \text{The formula is: }\;f(n) \;=\;A(1^n) + Bn(1^n) + C(2^n)$

And here's my other problem. Why do we raise the values of X to n-th power? Why is this function a sum of these powers anyway? And why is B multiplied by n, but A and C are not?

$\displaystyle \text{Use the first three terms of the sequence to create a system of equations.}$

Okay, the rest is obvious - we figure out the value of A, B and C and we get the function.

Sorry for the lack of correct English terms here and there.

See this theorem about the solution of a linear homogeneous recurrence relation with constant coefficients.