Recurrence Relation Initial Condition Question

Question

I have this problem:

Solve the recurrence \begin{cases} x(n) = x(n/2) + n & \text{for } n > 1, \\ x(1) = 1 & \end{cases} for $n = 2^k$.

The idea is to take the recurrence relation of $A(2^k)$, then swap it out for $n$ at the end. I've gotten to the point in my problem where I have found the common pattern, which is $$ A(2^{k-i}) + 2^{k-i} + 2^{k-(i-1)} + 2^{k-(i-2)}, $$ etc. Now, I'm unsure how to finish off this problem using the initial condition. I'm just not sure where to begin with the fact that $x(1) = 1$. Can anybody help me with this?

Answer 1

We can use the recurrence relation to generate the first few terms in the sequence: $$ x(2) = x(1) + 2 = 1 + 2 = 3, $$ and similarly, $$ x(4) = x(2) + 4 = 3 + 4 = 7, $$ and $$ x(8) = x(4) + 8 = 7 + 8 = 15. $$ Here are these values collected in a table. \begin{array}{c|c|c} k & 2^k & x(2^k) \\ \hline 0 & 1 & 1 \\ 1 & 2 & 3 \\ 2 & 4 & 7 \\ 3 & 8 & 15 \end{array}

Hopefully, you can see the pattern:

$$ x(2^k) = 2^{k+1} - 1, $$

which can be proved by induction on $k$.

Answer 2

After substitution , the recurrence reads

$$ x(2^k) = x(2^{k-1})+2^k $$

then calling $s(k) = x(2^k)$ the sequence can be recast as

$$ s(k) = s(k-1)+ 2^k $$

and now it is obvious that

$$ s(k) = c_0 + \sum_{j=0}^{j=k}2^j $$

and now as $x(1) = x(2^0) = s(0) = 1$ we have

$$ s(0) = c_0 + 1 = 1\Rightarrow c_0 = 0 $$

and the final solution is

$$ x(2^k) = s(k) = \sum_{j=0}^{j=k}2^j = \frac{2^{k+1}-1}{2-1} = 2n-1=x(n) $$