2
$\begingroup$

I'm working on solving some recurrence relations and following along with a couple of example solutions. One is my lecture notes. The other which closely matches in form is answered in this post: How to solve this recurrence $T(n) = 2T(n/2) + n\log n$

In this step...

$= 2[2W(k-2) + (k-1)2^{k-1}] + k2^k\\= 2^2W(k-2)+(k-1)2^k+ k2^k$

... $(k-1)2^{k-1}$ is simplified to $(k-1)2^k$ and it leaves me trying to figure out how that exponent is changing from $k-1$ to $k$. I'm looking at it like the $2$ multiplies across and I get $(2k-2)2^{k-1}$.

Can $(2k-2)2^{k-1}$ be simplified to $(k-1)2^k$?

$\endgroup$
2
  • $\begingroup$ $2\cdot 2^{k-1}=2^1\cdot 2^{k-1}=2^{1+(k-1)}=2^k$. For the other one, $2k-2=(k-1)\cdot 2$. $\endgroup$
    – vadim123
    Sep 10, 2015 at 4:25
  • $\begingroup$ $2^1*2^{k-1}$ is the hint that helped me solve $\endgroup$
    – ThisClark
    Sep 11, 2015 at 13:37

3 Answers 3

3
$\begingroup$

Something like this:

$$(2k-2)2^{k-1} =2(k-1)\frac{2^k}{2} = (k-1)2^k$$

$\endgroup$
1
$\begingroup$

Hint: $$a\cdot (b+c)=a\cdot b+a\cdot c=b\cdot a+c\cdot a=(b+c)\cdot a$$ $$a\cdot a^p=a^{p+1}$$

$\endgroup$
1
  • $\begingroup$ Your second edit ultimately brought me to the solution I posted below. $\endgroup$
    – ThisClark
    Sep 10, 2015 at 5:43
0
$\begingroup$

Reordering as in Cameron's hint brought me to the solution.

$2^{k-1}(2k-2) = 2k2^{k-1} - 2^12^{k-1}(k-1) = 2^k(k-1)$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .