Welcome to our community

Be a part of something great, join today!

Solving for specific variable when solving a recurrence equation

ATroelstein

New member
Jun 30, 2012
15
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
Mar 5, 2012
8,780
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
$$