CODEWITHSUNDEEP
algorithmrecursionmathfibonacci
echo Lee
echo Lee

Reputation: 341

How to solve a recurrence relation by unrolling?

If I have T(n) = T(n-1) + T(n-2)+ cn; T(1) = T(2) = d

How can I apply unrolling to solve a closed-form for T(n)?

When I try to unroll this by substitution, my equation gets really long and hard to keep track.

Upvotes: 0

Views: 821

Answers (2)

kaya3
kaya3

Reputation: 51034

Let's rearrange this to

T(n) - T(n-1) - T(n-2) = cn

Since the left-hand side is linear in T, there is a standard solution method: find the general solution, find any particular solution, and then find the right instance of the general solution to add to the particular solution in order to match the boundary conditions T(1) = T(2) = d.

General solution

We want to find all solutions to T′(n) - T′(n-1) - T′(n-2) = 0. A solution for T′(n) is not a solution to the original problem, because the right-hand-side is zero; but it's useful to solve this equation because by linearity, a solution to the original problem plus any solution to the "equals zero" problem gives another solution to the original problem.

This is a linear recurrence relation, so we can guess a solution has the form T′(n) = xn for some x ≠ 0. Substituting gives xn - xn-1 - xn-2 = 0, and dividing by xn-2 gives a quadratic equation x2 - x - 1 = 0. By applying the quadratic formula, this equation has two solutions, which happen to be the golden ratio x = φ, and x = -1/φ.

So T′(n) = φn and T′(n) = (-1/φ)n are both solutions, and since the equation is linear, any linear combination of these is also a solution. The general form is T′(n) = aφn + b(-1/φ)n where a and b are arbitrary constants.

Particular solution

We want to find any solution to T(n) - T(n-1) - T(n-2) = cn. Since the right-hand side is a degree-1 polynomial in n, we can guess that the solution has the form T(n) = pn + q for some p, q. Substituting this in gives

(pn + q) - (pn - p + q) - (pn - 2p + q) = cn

Equating coefficients, -pn = cn and 3p - q = 0, so we have p = -c and q = -3c, and hence the particular solution is T(n) = -cn - 3c.

Boundary conditions

So we are looking for values of a and b, such that

T(n) = aφn + b(-1/φ)n - cn - 3c

satisfies the boundary conditions T(1) = T(2) = d. Substituting in, we get

  • aφ + b(-1/φ) - c - 3c = d
  • aφ2 + b(-1/φ)2 - 2c - 3c = d

Since c, d and φ are constants, this is a system of two linear equations in two variables a and b. It can be solved by applying a standard technique such as elimination or substitution, or just plugged into Wolfram Alpha, giving the unique solution

solution for a and b

This can certainly be simplified to eliminate the square roots in the denominators, but I don't think that's necessary for the purposes of demonstrating the solution method.

Upvotes: 1

JohanC
JohanC

Reputation: 80319

You could use sympy, Python's symbolic math library to write out the terms.

from sympy.abc import c, d

def T(n):
    if n <= 0:
        return None
    elif n <= 2:
        return d
    else:
        return T(n-1) + T(n-2) + c*n

for i in range(1, 11):
    print(i, T(i))

This gives:

1 d
2 d
3 3*c + 2*d
4 7*c + 3*d
5 15*c + 5*d
6 28*c + 8*d
7 50*c + 13*d
8 86*c + 21*d
9 145*c + 34*d
10 241*c + 55*d

The coefficients for d are clearly the Fibonacci numbers. The coefficients for c can be looked up in oeis leading to A023552. This gives a long explicit formula, and also Fibonacci(n+2) + 2*Fibonacci(n) - (n+3).

Replacing Fibonacci with Binet's formula using sqrt(5), results in following expression for T(n):

-2**(-n)*(c*(20*2**n*n + 60*2**n + 8*sqrt(5)*((1 - sqrt(5))**n - (1 + sqrt(5))**n) + sqrt(5)*((1 - sqrt(5))**(n + 2) - (1 + sqrt(5))**(n + 2))) + 4*sqrt(5)*d*((1 - sqrt(5))**n - (1 + sqrt(5))**n))/20

This formula coincides nicely with the values above for n = 1 .. 10. But it doesn't look like a formula to be calculated 'by hand'. (Note that Python uses ** for power and reserves ^ for exclusive or.)

Alternatively, one could try Sympy's rsolve to get an explicit formula:

from sympy import Function, rsolve
from sympy.abc import n, c, d

f = Function('f')
T = f(n) - f(n-1) - f(n-2) - c*n
s = rsolve(T, f(n), {f(1): d, f(2): d})
print (s.simplify())

Which outputs:

2**(1 - n)*d*(-2**n*c*n - 2**(n + 1)*c + c*(1 + sqrt(5))**n - (1 - sqrt(5))**n + (1 + sqrt(5))**n)/(-5*c + sqrt(5)*c + 2*sqrt(5))

and which unfortunately seems to be wrong.

Upvotes: 1

Related Questions