Removing recursion from sequence

**Bivalgo** · May 29th 2011, 02:06 AM

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:

${a}_{1} = 1$
${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?

**FernandoRevilla** · May 29th 2011, 08:07 AM

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

**Soroban** · May 29th 2011, 08:25 AM

Hello, Bivalgo!

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

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

$\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}$

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

$\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}$

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

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

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

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

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

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

. . $\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}$

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

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

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

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

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

**Also sprach Zarathustra** · May 29th 2011, 10:12 AM

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:

${a}_{1} = 1$
${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 ${a}_{0} = 0$ .

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

So:

$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:

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

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

Or:

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

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

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

But this is a wrong answer!

Where is my mistake?
Thank you.

**Bivalgo** · Jun 1st 2011, 02:17 AM

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...

$\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}$

$\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...

$\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}$

$\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...

$\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?

$\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...

$\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...

$\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?

$\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.

**emakarov** · Jun 1st 2011, 02:59 AM

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

Thread: Removing recursion from sequence

LinkBack

Thread Tools

Display

Removing recursion from sequence

Similar Math Help Forum Discussions

Recursion sequence, and its limit

[SOLVED] Limit of a sequence - recursion

simplify by removing factors of 1

Removing (log) from an equality

Search Tags