Solve the recurrence

\[ \begin{aligned} A_N &= A_{N-1} - \frac{A_{N-1}}{N} + 2\big(1 - \frac{2A_{N-1}}{N} \big) & \text{for } N > 0 \text{ with } A_0 = 0.\\ \end{aligned} \]

Attempt:

\[ \begin{aligned} N A_N &= N A_{N-1} - 2A_{N-1} + 2N - 4A_{N-1} \\ &= (N - 6) A_{N-1} + 2N \\ A_N &= \frac{N - 6}{N} A_{N-1} + 2 \\ \frac{N!}{(N-6)!} A_N &= \frac{N!}{(N-6)!} \big(\frac{N - 6}{N} A_{N-1} + 2\big) & \text{divide by summation factor of }\frac{(N-6)!}{N!} \\ &= \frac{(N-1)!}{(N-7)!} A_{N-1} + 2 \frac{N!}{(N-6)!} \\ \frac{N!}{(N-6)!6!} A_N &= \frac{(N-1)!}{(N-7)!6!} A_{N-1} + 2 \frac{N!}{(N-6)!6!} & \text{divide by }6! \\ {N \choose 6} A_N &= {N-1 \choose 6} A_{N-1} + 2 {N \choose 6} & \text{note } N \text{ must be }> 6\\ &= {7 \choose 6} A_{7} + 2 {8 \choose 6} + \cdots + 2 {N \choose 6} & \text{telescope} \\ &= 7 A_{7} + 2 \sum_{k=8}^N {k \choose 6} \\ &= 7 A_{7} + 2 \sum_{k=0}^N {k \choose 6} - 2 \sum_{k=0}^7 {k \choose 6} \\ &= 7 A_{7} + 2 {N+1 \choose 6+1} - 2 {7+1 \choose 6+1} & \text{sum of binomial coefficients over upper index} \\ A_N &= \frac{1}{{N \choose 6}} \big(7 A_{7} + 2 {N+1 \choose 7} - 16 \big) \\ \end{aligned} \]

Recall \(A_N = \frac{N - 6}{N} A_{N-1} + 2\), and \(A_0 = 0\). So

\[ \begin{aligned} A_1 &= \frac{1 - 6}{1} A_0 + 2 = 2 \\ A_2 &= \frac{2 - 6}{2} A_1 + 2 = -2 \\ A_3 &= \frac{3 - 6}{3} A_2 + 2 = 4 \\ A_4 &= \frac{4 - 6}{4} A_3 + 2 = 0 \\ A_5 &= \frac{5 - 6}{5} A_4 + 2 = 2 \\ A_6 &= \frac{6 - 6}{6} A_5 + 2 = 2 \\ A_7 &= \frac{7 - 6}{7} A_6 + 2 = \frac{16}{7} \\ \therefore A_N &= \frac{1}{{N \choose 6}} \big(16 + 2 {N+1 \choose 7} - 16 \big) = \frac{2}{{N \choose 6}} {N+1 \choose 7} \\ &= \frac{2 (N+1)!}{7! (N+1-7)!}\cdot \frac{6! (N-6)!}{N!} \\ A_N &= \frac{2}{7}(N+1) & \text{!} \\ \end{aligned} \]

\(\Box\)

See: Sum of Binomial Coefficients over Upper Index

Source: Analysis of Algorithm

# posted by rot13(Unafba Pune) @ 9:21 PM