-2

I am trying to solve the recursion $T (k) = T (k/5) + k^2$ and I can't figure out after the following step. $$\begin{align}T(k) &= T (k/5) + k^2\\ &= (T(k/25) + k^2/25) + k^2\\ &= (T(k/625) + k^2/625) + k^2/25 + k^2\\ &= T(1) + … + k^2/625 + k^2/25 + k^2\\ &= k^2+ k^2/25+ k^2/625 +…+ T(1) \end{align}$$

saulspatz
  • 53,131
AMR
  • 1
  • this is a question that falls under the general category of functional equation which, in general means the "unknown" you're solving for represents a function. Typically, the function at a certain value will be related to the same function at other values and functions that satisfy this relation are said to be "solutions". Here is wolframs solution https://www.wolframalpha.com/input/?i=y%28x%29-y%28x%2F5%29%3Dx%5E2. In general, there is no clear cut method to solving these types of equations and in fact numerical analysis may be necessary. – Colin Hicks Sep 18 '19 at 00:51
  • Where did the $T(1)$ come from? As you use the recursive equation to expand, doesn’t that term approach $T(0)$, assuming the function is continuous, or else not necessarily approach anything, in which case why call it $T(1)$? – Joe Sep 18 '19 at 01:00
  • $1+1/25+1/625+\cdots=25/24$, so you might guess $T(k)=25k^2/24 + C$. – saulspatz Sep 18 '19 at 01:03

1 Answers1

1

You might just guess that $T(n)$ is of the form $an^2$, then $$T(k)=ak^2=T(\frac k5)+k^2=a(\frac k5)^2+k^2\\ ak^2=\frac a{25}k^2+k^2\\ a=\frac a{25}+1\\ a=\frac {25}{24}\\ T(k)=\frac {25}{24}k^2$$

Ross Millikan
  • 374,822
  • If $T(k)$ is continuous at $k=0$, then isn’t the general solution $\frac{25k^2}{24} +T(0)$, which can be determined straight from the geometric series? – Joe Sep 18 '19 at 01:05