1

I'd like to solve a recurrence, so I've been reading about solving recurrences, and all the ones I've seen solved involve only previous terms of the recurrence, and constants. My recurrence is

$$t(n) = \frac{t(n-1)(1-\ln(n-1))}{\ln n}$$

and if I could get help solving it, I'd be much obliged; but I'd especially like to know if there are any general principles for solving recurrences of this nature (with functions in them).

Henry T. Horton
  • 18,318
  • 5
  • 60
  • 77
Annick
  • 563

2 Answers2

3

When you have $t(n)=t(n-1)f(n)$ you can just write $t(n)=t(1)\prod_{i=2}^n f(i)$. In this case I started $i$ at $2$ because trying $n=1$ leads to division by zero. So $t(n)=t(1)\prod_{i=2}^n \frac {1-\ln (i-1)}{\ln i}$

Ross Millikan
  • 374,822
0

That is a linear recurrence of the first order. They can be solved in general.

Say you have $t_{n + 1} = a_n t_n + f_n$, $t_0$ given. You can divide by $\prod_{0 \le k \le n} a_k$ (as long as no $a_i = 0$) to get:

$$\frac{t_{n + 1}}{\prod_{0 \le k \le n} a_k} = \frac{t_n}{\prod_{0 \le k \le n - 1} a_k} + \frac{f_n}{\prod_{0 \le k \le n} a_k} $$

The change of variable $s_n = \frac{t_n}{\prod_{0 \le k \le n - 1} a_k}$ gives the telescoping:

$$s_{n + 1} - s_n = \frac{f_n}{\prod_{0 \le k \le n} a_k}$$

and the solution is a summation away.

vonbrand
  • 27,812