# Thread: Closed-form solution of a recurrence relation.

1. ## Closed-form solution of a recurrence relation.

Suppose you have a recurrence relation like:
$\displaystyle {x_{n + 2}} - 3{x_{n + 1}} + 2{x_n} = n{\rm$ (1)
With $\displaystyle {x_0} = {x_1} = 1$

And you want to find the closed form, of it ( i.e $\displaystyle {x_n}=f(n)$ ).
In the Mathematics for the analysis of Algorithms, by Knuth and Greene it has the following procedure:

We construct a function G(z): $\displaystyle G(z) = \sum\limits_i {{x_i}{z^i}}$

Then we multiply (1) by $\displaystyle {z^{n+2}}$ and sum over all n obtaining:
$\displaystyle \sum\limits_{n \ge 0} {{x_{n + 2}}{z^{n + 2}}} - 3z\sum\limits_{n \ge 0} {{x_{n + 1}}{z^{n + 1}}} + 2{z^2}\sum\limits_{n \ge 0} {{x_n}{z^n}} = \sum\limits_{n \ge 0} {n{z^{n + 2}}} \Rightarrow$
$\displaystyle (G(z) - z - 1) - 3z(G(z) - 1) + 2{z^2}G(z) = \frac{{{z^3}}}{{{{(1 - z)}^2}}} \Rightarrow$
$\displaystyle G(z) = \frac{{{z^3}}}{{{{(1 - z)}^2}(1 - 3z + 2{z^2})}} + \frac{{ - 2z + 1}}{{1 - 3z + 2{z^2}}}$

And now it says that we would like to recover the coefficient of $\displaystyle {z^n}$ in G(z).
a) But what does that mean? The only z powers i see in the last equation is $\displaystyle {z}$, $\displaystyle {z^2}$, $\displaystyle {z^3}$. So what coefficient of $\displaystyle {z^n}$ is he talking about?

And then it says that if the denominators of the fractions in G(z) where linear the recovery problem would be simple and that each term would just be a geometric series?
b) How come the last one? What exactly does it mean?

And now the most important question, which is about the derivation of the solution.
Book continues saying that since the denominators of the fractions in G(z) are not linear, we express the solution for G(z) in partial fractions so we obtain:
$\displaystyle G(z) = \frac{1}{{1 - 2z}} + \frac{1}{{{{(1 - z)}^2}}} - \frac{1}{{{{(1 - z)}^3}}}$ (2)

And now it says that we should note that the only nonlinear denominators are just higher powers of a linear factor.
So these terms can be expanded by the binomial theorem and then $\displaystyle {x_n}$ can be easily computed to be:
$\displaystyle {x_n} = {2^n} - \frac{{{n^2} + n}}{2}$

c) So my question is: How $\displaystyle {x_n}$ can be easily computed from (2)???? I don't get it.

Any help with a), b), c) questions and especially with c)?

2. ## Re: Closed-form solution of a recurrence relation.

We expand $\displaystyle G(z)$ in power series: $\displaystyle \frac 1{1-2z} = \sum_{n=0}^{+\infty}2^nz^n$; $\displaystyle \frac 1{(1-z)^2} = \sum_{n=1}^{+\infty}nz^{n-1}$; $\displaystyle \frac 1{(1-z)^3} =\frac 12\sum_{n=2}^{+\infty}n(n-1)z^{n-2}$.

3. ## Re: Closed-form solution of a recurrence relation.

Originally Posted by girdav
We expand $\displaystyle G(z)$ in power series: $\displaystyle \frac 1{1-2z} = \sum_{n=0}^{+\infty}2^nz^n$
$\displaystyle \frac 1{(1-z)^2} = \sum_{n=1}^{+\infty}nz^n$
$\displaystyle \frac 1{(1-z)^3} =\frac 12\sum_{n=2}^{+\infty}n(n-1)z^{n-2}$.
Is the second one a typo?
I mean the correct one should have been:
$\displaystyle \frac 1{(1-z)^2} = \sum_{n=1}^{+\infty}nz^{n-1}$
Right?

But even that way, i don't seem to derive the expected solution of:
$\displaystyle {x_n} = {2^n} - \frac{{{n^2} + n}}{2}$

Here is why:
$\displaystyle G(z) = \frac{1}{{1 - 2z}} + \frac{1}{{{{(1 - z)}^2}}} + \frac{1}{{{{(1 - z)}^3}}}\Rightarrow$
$\displaystyle G(z) = \sum\limits_{n = 0}^{ + \infty } {{2^n}{z^n}} + \sum\limits_{n = 1}^{ + \infty } {n{z^{n - 1}}} + \frac{1}{2}\sum\limits_{n = 2}^{ + \infty } {n(n - 1){z^{n - 2}}} \Rightarrow$
$\displaystyle G(z) = \sum\limits_{n = 0}^{ + \infty } {{2^n}{z^n}} + \sum\limits_{n = 0}^{ + \infty } {(n + 1){z^n}} + \frac{1}{2}\sum\limits_{n = 0}^{ + \infty } {(n + 2)(n + 1){z^n}} \Rightarrow$
$\displaystyle G(z) = \sum\limits_{n = 0}^{ + \infty } {\left( {{z^n}({2^n} + (n + 1) + (n + 2)(n + 1))} \right)} \Rightarrow$
$\displaystyle G(z) = \sum\limits_{n = 0}^{ + \infty } {\left( {{z^n}({2^n} + (n + 2)(n + 3))} \right)}$

So what is exactly the whole deal i'm missing? What i'm getting wrong?

4. ## Re: Closed-form solution of a recurrence relation.

Yes, the second one was a typo and I have corrected it.
There is a problem in (2): we have $\displaystyle G(0) =1$ whereas with (2) we get $\displaystyle G(0) =3$. I guess there should be a "-", but I didn't look where. You missed the $\displaystyle \frac 12$ between the lines 3 and 4 when you write $\displaystyle G(z)$ with power series.

5. ## Re: Closed-form solution of a recurrence relation.

Originally Posted by girdav
Yes, the second one was a typo and I have corrected it.
There is a problem in (2): we have $\displaystyle G(0) =1$ whereas with (2) we get $\displaystyle G(0) =3$. I guess there should be a "-", but I didn't look where. You missed the $\displaystyle \frac 12$ between the lines 3 and 4 when you write $\displaystyle G(z)$ with power series.
Yes the calculated G(z) in (2) i gave in the initial post** was wrong, there is a minus sign in the last term instead of a positive one i previously had .
So everything makes sense now, thanks.

**I corrected the initial post now.

6. ## Re: Closed-form solution of a recurrence relation.

Originally Posted by ChessTal
Suppose you have a recurrence relation like: $\displaystyle {x_{n + 2}} - 3{x_{n + 1}} + 2{x_n} = n{\rm$ (1) With $\displaystyle {x_0} = {x_1} = 1$
If you want to practice, here you have a similar problem I solved to the students of Industrial Engineering .

7. ## Re: Closed-form solution of a recurrence relation.

Originally Posted by ChessTal
Suppose you have a recurrence relation like:
$\displaystyle {x_{n + 2}} - 3{x_{n + 1}} + 2{x_n} = n{\rm$ (1)
With $\displaystyle {x_0} = {x_1} = 1$

And you want to find the closed form, of it ( i.e $\displaystyle {x_n}=f(n)$ ).
In the Mathematics for the analysis of Algorithms, by Knuth and Greene it has the following procedure:

We construct a function G(z): $\displaystyle G(z) = \sum\limits_i {{x_i}{z^i}}$

Then we multiply (1) by $\displaystyle {z^{n+2}}$ and sum over all n obtaining:
$\displaystyle \sum\limits_{n \ge 0} {{x_{n + 2}}{z^{n + 2}}} - 3z\sum\limits_{n \ge 0} {{x_{n + 1}}{z^{n + 1}}} + 2{z^2}\sum\limits_{n \ge 0} {{x_n}{z^n}} = \sum\limits_{n \ge 0} {n{z^{n + 2}}} \Rightarrow$
$\displaystyle (G(z) - z - 1) - 3z(G(z) - 1) + 2{z^2}G(z) = \frac{{{z^3}}}{{{{(1 - z)}^2}}} \Rightarrow$
$\displaystyle G(z) = \frac{{{z^3}}}{{{{(1 - z)}^2}(1 - 3z + 2{z^2})}} + \frac{{ - 2z + 1}}{{1 - 3z + 2{z^2}}}$

And now it says that we would like to recover the coefficient of $\displaystyle {z^n}$ in G(z).
a) But what does that mean? The only z powers i see in the last equation is $\displaystyle {z}$, $\displaystyle {z^2}$, $\displaystyle {z^3}$. So what coefficient of $\displaystyle {z^n}$ is he talking about?

And then it says that if the denominators of the fractions in G(z) where linear the recovery problem would be simple and that each term would just be a geometric series?
b) How come the last one? What exactly does it mean?

And now the most important question, which is about the derivation of the solution.
Book continues saying that since the denominators of the fractions in G(z) are not linear, we express the solution for G(z) in partial fractions so we obtain:
$\displaystyle G(z) = \frac{1}{{1 - 2z}} + \frac{1}{{{{(1 - z)}^2}}} - \frac{1}{{{{(1 - z)}^3}}}$ (2)

And now it says that we should note that the only nonlinear denominators are just higher powers of a linear factor.
So these terms can be expanded by the binomial theorem and then $\displaystyle {x_n}$ can be easily computed to be:
$\displaystyle {x_n} = {2^n} - \frac{{{n^2} + n}}{2}$

c) So my question is: How $\displaystyle {x_n}$ can be easily computed from (2)???? I don't get it.

Any help with a), b), c) questions and especially with c)?

The way to get (2) from (*)

(*) $\displaystyle \frac{z^3}{(1-z)^3(1-2z)}=\frac{z^2}{(1-z)^2}\cdot\frac{z}{(1-z)(1-2z)}=\big{(}\frac{z}{1-z}\big{)}^2\cdot\frac{z}{(1-z)(1-2z)}$

Now, $\displaystyle \frac{z}{1-z}=\frac{1-z-1}{1-z}=1-\frac{1}{1-z}$

and:

$\displaystyle \frac{z}{(1-z)(1-2z)}=\frac{1}{1-2z}-\frac{1}{1-z})$

Hence (*) becomes to:

$\displaystyle \big{(}1-\frac{1}{1-z}\big{)}^2\cdot\big{(}\frac{1}{1-2z}-\frac{1}{1-z}\big{)}=\big{(}1-\frac{2}{1-z}+\frac{1}{(1-z)^2}\big{)}\big{(}\frac{1}{1-2z}-\frac{1}{1-z}\big{)}=\frac{1}{1-2z}-\frac{1}{1-z}-\frac{2}{(1-z)(1-2z)}+\frac{2}{(1-z)^2}+\frac{1}{(1-z)^2(1-2z)}-\frac{1}{(1-z)^3}$

But:

$\displaystyle -\frac{2}{(1-z)(1-2z)}+\frac{1}{(1-z)^2(1-2z)}=\frac{1}{1-2z}\big{(}\frac{1}{(1-z)^2}-\frac{2}{1-z}\big{)}=\frac{1}{1-2z}\frac{2z-1}{(1-z)^2}=-\frac{1}{(1-z)^2}$

So:

$\displaystyle \frac{1}{1-2z}-\frac{1}{1-z}-\frac{2}{(1-z)(1-2z)}+\frac{2}{(1-z)^2}+\frac{1}{(1-z)^2(1-2z)}-\frac{1}{(1-z)^3}=\frac{1}{1-2z}-\frac{1}{1-z}+\frac{2}{(1-z)^2}-\frac{1}{(1-z)^3}-\frac{1}{(1-z)^2}=\frac{1}{1-2z}-\frac{1}{1-z}-\frac{1}{(1-z)^3}+\frac{1}{(1-z)^2}$