Solve the recurrence:

\[ \begin{aligned} A_N &= 1 + \frac{2}{N}\sum_{j=1}^N A_{j-1} &\text{ for } N > 0 \\ N A_N &= N + 2\sum_{j=1}^N A_{j-1} \\ (N-1) A_{N-1} &= (N-1) + 2\sum_{j=1}^{N-1} A_{j-1} &\text{for } N-1 \text{ instead of } N \\ NA_N - (N-1)A_{N-1} &= 1 + 2A_{N-1} &\text{subtract the last two equations}\\ NA_N &= (N+1)A_{N-1} + 1 &\text{note it's now linear time, not quadratic!}\\ \frac{A_N}{N+1} &= \frac{A_{N-1}}{N} + \frac{1}{N(N+1)} &\text{divide both sides by } N(N+1) \\ \frac{A_N}{N+1} &= \frac{A_{1}}{2} + \frac{1}{2 \cdot 3} + \cdots + \frac{1}{N(N+1)} &\text{telescope} \\ &= \frac{1}{1 \cdot 2} + \frac{1}{2 \cdot 3} + \cdots + \frac{1}{N(N+1)} &\text{note }A_1 = 1 \text{, assuming } A_0 = 0 \\ A_N &= (N+1) \sum_{k=1}^N \frac{1}{k(k+1)} \\ &= (N+1) \sum_{k=1}^N (\frac{1}{k} - \frac{1}{k+1}) & \text{partial fraction} \\ &= (N+1) (1 - \frac{1}{N+1}) & \text{telescoping series} \\ A_N &= N & \Box \\ \end{aligned} \]

Alternatively, instead of using telescoping series,

\[ \begin{aligned} A_N &= (N+1) \sum_{k=1}^N (\frac{1}{k} - \frac{1}{k+1}) \\ A_N &\thicksim N \sum_{k=1}^N (\frac{1}{k} - \frac{1}{k+1}) & f(x) \thicksim g(x) \text{ means} \lim_{x\rightarrow\infty}\frac{f(x)}{g(x)} = 1 \\ &= N \big(\sum_{k=1}^N \frac{1}{k} - \sum_{k=1}^N \frac{1}{k+1}\big) \\ \end{aligned} \]

By the definition of Euler's constant,

\[ \begin{aligned} \gamma &= \lim_{N \rightarrow \infty} \big( \sum_{k=1}^N \frac{1}{k} - \ln N \big) \\ \therefore \lim_{N \rightarrow \infty} \big( \sum_{k=1}^N \frac{1}{k} &= \ln N + \gamma \big) \\ \gamma &= 1 + \lim_{N \rightarrow \infty} \big( \sum_{k=2}^N \frac{1}{k} - \ln N \big) & \text{pull out the 1st term} \\ &= 1 + \lim_{N \rightarrow \infty} \big( \sum_{k=1}^{N-1} \frac{1}{k+1} - \ln N \big) & \text{re-index} \\ \lim_{N \rightarrow \infty} \big( \sum_{k=1}^{N-1} \frac{1}{k+1} &= \ln N + \gamma - 1 \big) \\ \therefore \lim_{N \rightarrow \infty} \big( \sum_{k=1}^{N} \frac{1}{k+1} &= \ln (N+1) + \gamma - 1 \big) & \text{for } N+1 \text{ instead of } N \\ \end{aligned} \]

Hence

\[ \begin{aligned} A_N &\thicksim N \big(\sum_{k=1}^N \frac{1}{k} - \sum_{k=1}^N \frac{1}{k+1}\big) \\ A_N &\thicksim N \big[ \big(\ln N + \gamma\big) - \big(\ln (N+1) + \gamma - 1\big) \big] \\ A_N &\thicksim N \big(\ln N - \ln (N+1) + 1\big) \\ A_N &\thicksim N &\Box \\ \end{aligned} \]

Source: Analysis of Algorithm

# posted by rot13(Unafba Pune) @ 9:27 AM