# Solving for specific variable when solving a recurrence equation

#### ATroelstein

##### New member
I have the following recurrence equation, where C is just some constant:
$$T(n) = 0, n = 1\\ T(n) = T(\frac{n-1}{2}) + 2C, n > 1$$

Using a top-down approach to unrolling the equation to find the pattern, I get:

$$T(n) = T(\frac{n-k}{2^{k}}) + 2kC$$

Now I want to solve for k and associate it with n to finish solving the equation without k in it. In order to get:

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

Then:

$$n-k = 2^{k}$$

The problem I am running into is that I'm having trouble solving this for k. I have worked through many other examples where:

$$n = 2^{k}$$

and then I know:

$$k = log_2 n$$

But having the n-k is making it difficult for me to solve for k. Thanks in advance.

#### Klaas van Aarsen

##### MHB Seeker
Staff member
Using a top-down approach to unrolling the equation to find the pattern, I get:

$$T(n) = T(\frac{n-k}{2^{k}}) + 2kC$$
Hi ATroelstein!

The equation you're trying to solve is not very solvable.

But perhaps you could redo the unrolling of the equation and get:
$$T(n) = T\left(\frac{n-2^k+1}{2^k}\right) + 2kC$$