How would I put these recurrence relation terms into a summation?

233 Views Asked by At

I was given these terms as part of a recurrence relation and I need to put it into a summation in order to solve it. $T(n)=2^{k}T\left(\dfrac{n}{2^{k}}\right) + 2^{k-1}T\left(\dfrac{n}{2^{k-1}}\right) + ... +\dfrac{n^{2}}{4}+8+\dfrac{n^2}{2}+4+n^2+2+2n^{2}+1$

The term $2^{k}T\left(\dfrac{n}{2^{k}}\right)$ is $0$ based on the assumption that $k=\log_{2}n$ and that $T(1)=0$.

I have tried putting these terms in a summation and this is what I have so far

$\sum\limits_{i=0}^{k-1}\dfrac{n^2}{2^{i-1}}+2^{i}$

I am not sure if this is the correct expression because I cannot get this into an expression with a known formula. I know the geometric sum formula but simplifying the first term in the summation will give a negative exponent and I don't think that works with the geometric sum.

The answer that was given in the problem was $T(n)=4n^{2}-3n-1$. Could someone explain what I am doing wrong?

*edit

Here is what I have tried so far

$\sum\limits_{i=0}^{k-1}\dfrac{n^{2}}{2^{i-1}}+2^{i} =n^{2}\sum\limits_{i=0}^{k-1}\dfrac{1}{2^{i-1}}+\sum\limits_{i=0}^{k-1}2^{i}$

I then simplified $\dfrac{1}{2^{i-1}}$ to $\dfrac{2}{2^{i}}$ and now I have

$2n^{2}\sum\limits_{i=0}^{k-1}\dfrac{1}{2^{i}}+\sum\limits_{i=0}^{k-1}2^{i}$

I know there is a formula for $\sum\limits_{i=0}^{k-1}2^{i}$ but I am having trouble with $\sum\limits_{i=0}^{k-1}\dfrac{1}{2^{i}}$, I can use the exponent trick to turn $\dfrac{1}{2^{i}}$ into $2^{-i}$ but I do not know of any formula that works for $\sum\limits_{i=0}^{k-1}2^{-i}$. That is the part I am stuck on.