somatorias. Melhor ainda, essa recorrencia esta no ponto certo para usar a tecnica do summation factor! Como esse e um truque muito util de se conhecer, eu vou fazer em camera lenta. Voce pode usar um summation factor sempre que sua recorrencia for da forma abaixo:$$a_n F[n] = b_n F[n-1]+c_n$$Esse e o nosso caso, se usarmos a correspondencia abaixo:$$\begin{align*}a_n &= n^2 \\b_n &= n^2-1 \\c_n &= 2n-1\end{align*}$$O segredo do summation faction e tentar achar uma sequencia magica ##s_n## que tenha a seguinte propriedade:$$s_n b_n=s_{n-1}a_{n-1}$$E por que isso e bom? Olha so o que acontece quando voce multiplica a recorrencia original por ##s_n##:$$\begin{align*}a_n F[n] &= b_n F[n-1]+c_n \\s_n a_n F[n] &= s_n b_n F[n-1]+s_n c_n \\s_n a_n F[n] &= s_{n-1}a_{n-1}F[n-1]+s_n c_n \\\end{align*}$$Agora, se voce substituir ##T[n]=s_n a_n F[n]##, temos:$$\begin{align*}s_n a_n F[n] &= s_{n-1}a_{n-1}F[n-1]+s_n c_n \\T[n] &= T[n-1]+s_n c_n\end{align*}$$Opa, essa e facil! Da pra resolver de cabeca, e praticamente a definicao de somatoria!$$\begin{align*}T[n] &= T[n-1]+s_n c_n\\T[n] &= T[0] + \sum_{1\le k \le n} s_k c_k \\s_n a_n F[n] &= s_0 a_0 F[0] + \sum_{1\le k \le n} s_k c_k \\ F[n] &= \frac{1}{s_n a_n} \left(s_0 a_0 F[0] + \sum_{1\le k \le n} s_k c_k \right) \\\end{align*}$$Pronto, agora nao e mais uma recorrencia, e uma formula simples. A dificuldade do metodo e encontrar o tal do ##s_n##. Para acha-lo voce pode usar a intuicao, chutar, fazer um sacrificio aos deuses; ou entao voce pode usar o metodo do porradao. Nesse metodo voce comeca com ##s_n=s_{n-1}\left(a_{n-1}/b_n\right)## e abre recursivamente, chegando no monstrinho abaixo:$$s_n = \frac{a_{n-1}a_{n-2}\ldots a_2 a_1}{b_n b_{n-1}\ldots b_3 b_2}$$Essa formula parece grande, e e grande mesmo. Mas na maioria das vezes tem um monte de cancelamentos, o que deixa o resultado final pequeno. Vamos ver no nosso caso como fica:$$\begin{align*}s_n &= \frac{a_{n-1}a_{n-2}\ldots a_2 a_1}{b_n b_{n-1}\ldots b_3 b_2} \\ &= \frac{(n-1)^2 (n-2)^2 \ldots 2^2 1^2} {\left(n^2-1\right) \left(\left(n-1\right)^2-1\right) \ldots (3^2-1) (2^2-1)} \\ &= \frac{(n-1)^2 (n-2)^2 \ldots 2^2 1^2} {\left((n+1)(n-1)\right) \left((n-1+1)(n-1-1)\right) \ldots (3+1)(3-1) (2+1)(2-1)} \\ &= \frac{(n-1) (n-2)(n-3) \ldots3\cdot 2\cdot 1} {(n+1) (n) (n-1)\ldots (4+1) (3+1) (2+1)} \\ &= \frac{2} {(n+1) (n) } \\\end{align*} $$Cancelou mesmo! Bastou lembrar que ##(a^2-b^2)=(a+b)(a-b)## que o resto saiu. Agora e so lembrar que ##F[0]=0## e substituir na formula:$$\begin{align*} F[n] &= \frac{1}{s_n a_n} \left(s_0 a_0 F[0] + \sum_{1\le k \le n} s_k c_k \right) \\ F[n] &= \frac{n(n+1)}{2n^2} \sum_{1\le k \le n} \frac{2(2k-1)}{k(k+1)}\\\end{align*}$$Essa e a solucao da recorrencia. Da para achar uma forma fechada? Nesse caso da, desde que voce tope uma forma fechada em funcao dos numeros harmonicos ##H[n]##, que sao definidos como:$$H[n]=\sum_{1\le k \le n}\frac{1}{k}$$Voce comeca abrindo a fracao no somatorio:$$\begin{align*} \frac{2(2k-1)}{k(k+1)} &= \frac{A}{k} + \frac{B}{k+1}\\ \frac{4k-2}{k(k+1)} &= \frac{A(k+1)+B k}{k(k+1)}\\ 4k-2 &= Ak+A +B k \\ 4k-2 &= (A+B)k+A \\ A &= -2 \\ B &= 6\end{align*}$$Agora voce divide o somatorio em dois:$$\begin{align*} F[n] &= \frac{n(n+1)}{2n^2} \sum_{1\le k \le n} \frac{2(2k-1)}{k(k+1)}\\ F[n] &= \frac{n(n+1)}{2n^2} \sum_{1\le k \le n} \frac{6}{k+1} - \frac{2}{k}\\ F[n] &= \frac{n(n+1)}{2n^2} \left( \sum_{1\le k \le n} \frac{6}{k+1} - \sum_{1\le k \le n} \frac{2}{k} \right) \\ F[n] &= \frac{n(n+1)}{2n^2} \left( \sum_{1\le k \le n} \frac{6}{k+1} - 2\sum_{1\le k \le n} \frac{1}{k} \right) \\ F[n] &= \frac{n(n+1)}{2n^2} \left( \sum_{1\le k