# Struggling with Recurrence Relation using Telescoping Approach

I have the following recurrence relation that I am trying to solve using the telescoping approach: $$T(n) = \begin{cases} T(\frac{n}{4})+ n^2 & \text{for } n \geq 4 \\ 1 & \text{otherwise} \end{cases}$$

I have this so far:

$$T(n) = T(\frac{n}{4}) + n^2$$

$$T(\frac{n}{4}) = T(\frac{n}{16}) + (\frac{n^2}{16})$$

$$T(\frac{n}{16}) = T(\frac{n}{64}) + (\frac{n^2}{256})$$ ... up to $$T(n) = 1$$

I know I am supposed to now write $$T(n)$$ as a sum of these expansions but I dont seem to be doing it right. I have:

$$T(n) = n^2 + (\frac{n}{4})^2 + (\frac{n}{16})^2 + (\frac{n}{64})^2$$ and so on.

Sorry for the poor formatting of my question, I am new to Stack Exchange. Please give me suggestions on formatting so I can edit it.

I am not so sure what the problem is: is it a problem on writing the formula with the sum, or finding a closed formula for the sum?

In the first case, you could write either: $$T(n) = n^2 + \left(\frac{n}4\right)^2 + \left(\frac{n}{16}\right)^2 … + 1$$

but that hides the number of terms.

Another possibility is writing:

$$T(n) = \sum\limits_{k=0}^{\log_4 n}\left(\frac{n}{4^k}\right)^2$$

Now for solving this, you just need to note that $$T(n) = n^2\sum\limits_{k=0}^{\log_4 n}\frac{1}{16^k}$$.

You can either find a formula for the sum: $$\sum\limits_{k=0}^{\log_4 n}\frac{1}{16^k} = \frac{1-\frac{1}{16^{\log_4 n + 1}}}{1 - \frac{1}{16}} = \frac{16-\frac{1}n}{15}$$ or simply an upper bound: $$\sum\limits_{k=0}^{\log_4 n}\frac{1}{16^k} \leqslant \sum\limits_{k=0}^{+\infty}\frac{1}{16^k} = \frac{1}{1- \frac{1}{16}} = \frac{16}{15}$$

• Thanks for your help. The question I was asked is: Given the following recurrence equation of T(n), express T(n) in an asymptotic big-O function from. Use the telescoping approach. State any simplifying assumption you are making. It suffices to derive the functional form only; there is no need to prove it by the formal definition of big-O. Oct 27, 2023 at 22:49
• Well you have enough information to solve it using my answer, don't you? Oct 27, 2023 at 23:22