If you were also interested in finding an explicit formula for T(n)
this may help.
We know that T(1) = c
and T(2) = 2c
and T(n) = T(n-1) + T(n-2) + c
.
So just write T(n)
and start expanding.
T(n) = T(n-1) + T(n-2) + c
T(n) = 2*T(n-2) + T(n-3) + 2c
T(n) = 3*T(n-3) + 2*T(n-4) + 4c
T(n) = 5*T(n-4) + 3*T(n-5) + 7c
and so on.
You see the coefficients are Fibonacci numbers themselves!
Call F(n)
the nth
Fibonacci number. F(n) = (phi^n + psi^n)/sqrt(5)
where phi = (1+sqrt(5))/2
and psi = -1/phi
, then we have:
T(n) = F(n)*2c + F(n-1)*c + (F(n+1)-1)*c
Here is some quick code to demonstrate:
def fib_gen(n):
"""generates fib numbers to avoid rounding errors"""
fibs=[1,1]
for i in xrange(n-2):
fibs.append(fibs[i]+fibs[i+1])
return fibs
F = fib_gen(50) #just an example.
c=1
def T(n):
"""the recursive definiton"""
if n == 1:
return c
if n == 2:
return 2*c
return T(n-1) + T(n-2) + c
def our_T(n):
n=n-2 #just because your intials were T(1) and T(2), sorry this is ugly!
"""our found relation"""
return F[n]*2*c + F[n-1]*c + (F[n+1]-1)*c
and
>>> T(24)
121392
>>> our_T(24)
121392