4

I've been trying to learn how to solve some recurrence relations lately and I have no idea how I would go about solving something like this, if possible.

$T(n) = a \cdot T(n-1) + b \cdot \sqrt{T(n-1)}$

My main problem is that I have no idea how to work with the square root term. The context of this problem is actually in economics. When looking at the level of capital at some time $t$ it's equal to some depreciation rate constant, $a$ times the capital at time $t-1$ added to some savings rate constant, $b$, times the output level at time $t-1$. In a basic case we consider output to be the square root of capital and that's why there is a square root term.

I spent some time trying random things and didn't have much luck so any help, if possible, would be greatly appreciated!

Thomas Granderson
  • 41

2 Answers2

1

Henceforth we assume $a,b$ are each in the interval $(0,1)$, as mentioned in the comments (excluding the endpoints as those lead to weird behavior).

Set $S(n)=\sqrt{T(n)}$; this satisfies $$S(n)=\sqrt{a S(n-1)^2+bS(n-1)}$$

We can find its fixed points by solving $S=\sqrt{aS^2+bS}$; they are $S=0$ and $S=\frac{b}{1-a}$. We wish to prove that $\frac{b}{1-a}$ is attractive. We set $f(x)=\sqrt{ax^2+bx}$, and (with the aid of a little alpha) calculate $$f'\left(\frac{b}{1-a}\right)=\frac{a+1}{2}$$

Since $|\frac{a+1}{2}|<1$, the iterated function will always converge.

Hence, the sequence $T(n)$ will always tend to $\frac{b^2}{(1-a)^2}$ as $n\to \infty$.

vadim123
  • 82,796
0

It seems to me like it would be easier to model the problem as a differential equation rather than a recurrence relation. That is, we'd have an equation of the form $$\frac{dT}{dt} = aT + b\sqrt{T} \text{.}$$ That differential equation is separable; solving it is only as hard as integrating $\int \frac{1}{aT + b\sqrt{T}} dT$. You can integrate that term by rationalizing the denominator and using partial fractions.

In the end, you'll get an equation that describes the solution implicitly, i.e. in the same sense that $x^2 + y^2 = 1$ describes the unit circle. Also, if your actual problem really is discrete in time, this will obviously only approximate the correct answer. However, even with both of these caveats, the solution will give you quite a bit of asymptotic information. And, if you need to compute precise values, you can just have a computer calculate terms of the recurrence directly.

In general, keep in mind that, while differential equations may seem more complicated than recurrences, calculus is actually very powerful and makes differential equations generally easier to work with.