Solving potentially infinite recurrence relation

Question

I want to solve $T(n) = T(\frac{1}{8n}) + 8$, it seems to me that the answer must be infinite since

\begin{align*} T(n) = T(\frac{1}{8n}) + 8 = T(\frac{1}{8(1/8n)}) + 2 \times 8 = T(n) + 16 \end{align*} and so $T(n) = \infty$. Is this correct?

Answer 1

You are correct! Here is your method explained slightly clearer:

Let $n=1$. Then, we have $\displaystyle T(1) = T(\frac{1}{8 \cdot 1}) + 8;\ T(1) = T(\frac{1}{8})+8. \quad(\text{equation } 1)$

Now let $n=\frac{1}{8}$. We get $\displaystyle T(\frac{1}{8}) = T(\frac{1}{\frac{1}{8} \cdot 8}) + 8;\ T(\frac{1}{8}) = T(1)+8. \quad(\text{equation } 2)$

Substituting equation $1$ into equation $2$, we have $T(1) = \big(T(1) + 8\big) + 8$. This shows that $0=16$, so the recurrence relation either is infinite, or has no solution.