Can You Solve This Recurrence Using the Recursion Tree Method?

[22990atinesh]

Homework Statement

$T(n) = 2 T(n-1) + n, n \geq 2$
$T(1) = 1$

Homework Equations

The Attempt at a Solution

I'm using recursion tree method to solve the above recurrence

T(n) = Summation of non-leaf nodes + leaf nodes
$T(n) = n + 2(n-1) + 2^2(n-2) + ... + 2^{n-1}$

 

[jedishrfu]

So what is your question?

 

[NascentOxygen]

This thread recurrs thrice.

 

[rcgldr]

Each thread had a separate problem. Maybe they should have been combined.

T(n+1) = T(n) + floor(sqrt(n+1))
T(1) = 1.
(I assumed that ⌊ ⌋ meant the integer floor of the sqrt).

Note that floor(sqrt(1->3)) = 1, floor(sqrt(4 -> 8)) = 2, floor(sqrt(9->15)) = 3, ... .

T(m^2) = m + 1*0 + 3*1 + 5*2 + 7*3 + ... + (2m-1)(m-1)
T(m^2) = m + sum i=1 to m: (2i - 1)(i - 1)

Which is a cubic equation of the form (I'll let you solve this one):

T(m^2) = a m^3 + b m^2 + c m

I don't know if there's a more generic method to solve this.

- - -

T(n) = 2 T(n/2) + 2
T(1)=2

n=2                               2
                           2             2n=4                               2
                           2             2
                        2     2       2     2  n=8                               2
                           2             2
                        2     2       2     2  
                       2 2   2 2     2 2   2 2

sum i=1 to log2(2n) : 2^i
2 T(n) - T(n) = T(n):

2 T(n) =        4 + 8 + 16 + ... + 2^(log2(2n)) + 2^(log2(4n))
  T(n) =    2 + 4 + 8 + 16 + ... + 2^(log2(2n))
----------------------------------------
  T(n) =   -2                                   + 2^(log2(4n))
  T(n) =   -2                                   + 4n
  T(n) = 4n - 2

- - -

For the summation series in the first post above, I used power series method, subracting 1 x series from 2 x series:

2(T(n)) =        (2)(n  ) + (2^2)(n-1) + (2^3)(n-2) + ... + 2^(n-1)(2) + 2^(n)
  T(n)  = (1)n + (2)(n-1) + (2^2)(n-2) + (2^3)(n-3) + ... + 2^(n-1)(1)
----------------------------------------------------------------------------
  T(n)  =   -n + (2)      + (2^2)      + (2^3)            + 2^(n-1)    + 2^(n)

2(T(n)+n) =       (2^2) + (2^3) + ... + 2^(n-1) + 2^(n) + 2^(n+1)
  T(n)+n  = (2) + (2^2) + (2^3) + ... + 2^(n-1) + 2^(n)
-----------------------------------------------------------------
  T(n)+n  = -2                                          + 2^(n+1)

T(n) = 2^(n+1) - n - 2

 

[Mark44]

This thread recurrs thrice.

The other two copies have been deleted.

Edit: The other two copies were deleted in error. They have been reinstated.

 

[22990atinesh]

...
For the summation series in the first post above, I used power series method, subracting 1 x series from 2 x series:

2(T(n)) =        (2)(n  ) + (2^2)(n-1) + (2^3)(n-2) + ... + 2^(n-1)(2) + 2^(n)
  T(n)  = (1)n + (2)(n-1) + (2^2)(n-2) + (2^3)(n-3) + ... + 2^(n-1)(1)
----------------------------------------------------------------------------
  T(n)  =   -n + (2)      + (2^2)      + (2^3)            + 2^(n-1)    + 2^(n)

2(T(n)+n) =       (2^2) + (2^3) + ... + 2^(n-1) + 2^(n) + 2^(n+1)
  T(n)+n  = (2) + (2^2) + (2^3) + ... + 2^(n-1) + 2^(n)
-----------------------------------------------------------------
  T(n)+n  = -2                                          + 2^(n+1)

T(n) = 2^(n+1) - n - 2

as the height of the tree is n-1. So series would be
$T(n) = n + 2(n-1) + 2^2(n-2) + ... + 2^{n-3}(n-[n-3]) + 2^{n-1}$
on solving with your approach I'm ending up with different ans
$2T(n) - T(n) = T(n) = n + 2 + 2^2 + 2^3 + ... + 2^{n-3} + 2{n-2}(n-[n-3]) + 2^{n-1} + 2$
$T(n) = n -1 - \frac{7}{2} 2^n$

 

[rcgldr]

So series would be
$T(n) = n + 2(n-1) + 2^2(n-2) + ... + 2^{n-3}(n-[n-3]) + 2^{n-1}$

A terms is missing, it should be:

$T(n) = n + 2(n-1) + 2^2(n-2) + ... + 2^{n-3}(3) + 2^{n-2}(2)+ 2^{n-1}$

Then 2 T(n) - T(n) is

$-n + 2 + 2^2 + 2^3 + ... + 2^n$

and you continue with T(n)+n as shown in my previous post.

 

[22990atinesh]

hmm Sorry little mistake

$T(n) = n + 2(n-1) + 2^2(n-2) + ... + 2^{n-2}(n-[n-2]) + 2^{n-1}$
$2*T(n) = 2*n + 2^2(n-1) + 2^3(n-2) + ... + 2^{n-1}(n-[n-2]) + 2^{n}$

$2*T(n) - T(n) = - n + 2 + 2^2 + ... + 2^{n-2} + 2^{n-1} + 2^n$
$T(n) = - n + 2 + 2^2 + ... + 2^{n-2} + 2^{n-1} + 2^n + 2^0 - 2^0$
$T(n) = - n + 2^0 + 2^1 + 2^2 + ... + 2^{n-2} + 2^{n-1} + 2^n - 2^0$
Now We can directly apply sum of GP formula here

$T(n) = - n + \frac{2^{n+1} -1}{2-1} - 2^0$
$T(n) = 2^{n+1} - n - 2$

By the way what is this "Power Series Method". All I can find on internet is "Power Series Method" for differential equations.

 

[rcgldr]

By the way what is this "Power Series Method".

I should have called it power series summation or geometric series. WIki articles:

http://en.wikipedia.org/wiki/Power_series

http://en.wikipedia.org/wiki/Geometric_series