Sum from $i$ to $\lg(n)$

Question

I am trying to find the solution for the recurrence equation using substitution :

$$tn=3\cdot t(n/2)+n\quad \text{ where } \quad t1=1/2$$

for $n >1$, $n$ a power of $2$.

I am stuck at

$$tn = 3^{\lg n} + n \cdot\sum\limits_{i=1}^{\lg n-1} \left(\frac{3}{2}\right)^{\lg n - i} $$

I checked this question, but still not able to figure out how to solve the above equation.

score 1 · Accepted Answer · answered Sep 13 '15 at 20:17

1

To me it's easier not to start with a version with logarithms.

Writing down the first few terms,

$t_1 = \frac{1}{2}$

$t_2 = \frac{3}{2} + 2 $

$t_4 = 3\cdot (\frac{3}{2} +2) + 4$

$t_8 = 3\cdot ( 3\cdot (\frac{3}{2} +2) + 4 ) + 8$

etc.

it becomes clear that we can write this in closed form as $t_{2^n} = \frac{3^n}{2} + \sum_{i=0}^{n-1}3^i 2^{n-i} = \frac{3^n}{2} + 2^n\sum_{i=0}^{n-1} (\frac{3}{2})^i = \frac{3^n}{2} + 2^n \cdot\frac{(\frac{3}{2})^n -1}{\frac{3}{2}-1} = \frac{3^n}{2}+2\cdot 3^n-2^{n+1}$

$ =\frac{5}{2}\cdot 3^n - 2^{n+1}$

We could also write this with logarithms as

$t_n = \frac{5}{2} \cdot 3^{log_2(n)} - 2n = \frac{5}{2}\cdot n^{log_2(3)}-2n$

answered Sep 13 '15 at 20:17

user35359

1,359

great. that helped :) – vishnu viswanath Sep 13 '15 at 20:33
You have shown this for $t_m$, where $m = 2^n$ for some $n$. You have not yet shown this for general $m$. – marty cohen Sep 13 '15 at 20:39
@sonic: You are welcome. marty:The $t_n$ are only defined for $n$ a power of 2. – user35359 Sep 13 '15 at 20:53
@user35359 : can you explain how the conversion to log was done? – vishnu viswanath Sep 15 '15 at 00:48
1

Well if $m = 2^n$, then by definition of the logarithm $n = log_2(m)$. So if $t_{2^n}$ can be decribed with some formula depending with variable $n$, $t_{2^n} = f(n)$, then $t_m = f(log_2(m))$. So I replaced every instance of $n$ in the formula $f(n)$ by $log_2(n)$ and simplified. – user35359 Sep 15 '15 at 01:34
ok. got it.. thnk u – vishnu viswanath Sep 15 '15 at 01:41

Sum from $i$ to $\lg(n)$

1 Answers1