A sequence $(a_n)$ is defined recursively by $a_1=0, a_2=1$ and for $n\ge 3$, \[a_n=\frac12na_{n-1}+\frac12n(n-1)a_{n-2}+(-1)^n\left(1-\frac{n}{2}\right).\] Find a closed-form expression for $f_n=a_n+2\binom{n}{1}a_{n-1}+3\binom{n}{2}a_{n-2}+\ldots +(n-1)\binom{n}{n-2}a_2+n\binom{n}{n-1}a_1$.
Problem
Source: Chinese Mathematical Olympiad 2000 Problem 2
Tags: algebra unsolved, algebra
25.08.2013 01:38
$a_n=n!\sum_{k=2}^n\frac{(-1)^k}{k!}$ $\frac{f_n}{n!}=\sum_{i=0}^{n-2}\frac{i+1}{i!}\sum_{k=2}^{n-i}\frac{(-1)^k}{k!}\\=\sum_{i=0}^{n-2}\frac{1}{i!}\sum_{k=2}^{n-i}\frac{(-1)^k}{k!}+\sum_{i=1}^{n-2}\frac{1}{(i-1)!}\sum_{k=2}^{n-i}\frac{(-1)^k}{k!}\\ =\sum_{i=0}^{n-2}\frac{1}{i!}\sum_{k=2}^{n-i}\frac{(-1)^k}{k!}+\sum_{i=0}^{n-3}\frac{1}{(i)!}\sum_{k=2}^{n-i-1}\frac{(-1)^k}{k!} \\=\sum_{t=2}^{n}\sum_{k=2}^{t}\frac{(-1)^k}{(t-k)!k!}+\sum_{t=2}^{n-1}\sum_{k=2}^{t}\frac{(-1)^k}{(t-k)!k!}\\=\sum_{t=2}^{n}\frac{t-1}{t!}+\sum_{t=2}^{n-1}\frac{t-1}{t!}.$ The last step uses $0=t!\sum_{k=0}^t\frac{(-1)^k}{(t-k)!k!}$. Now it is easy to see $\frac{f_n}{n!}=1-\frac1{n!}+1-\frac1{(n-1)!}$ So $f_n=2n!-n-1$.
26.10.2016 17:01
Is there any solution without algebra?
12.06.2017 00:04
Solution: Let $b_n=\frac{a_n}{n!}$, then $b_1=0, b_2=\frac{1}{2}, b_3=\frac{1}{3}$, $b_n=\frac{1}{2} (b_{n-1}+b_{n-2}) +(-1)^n \cdot \frac{1-\frac{n}{2}}{n!}$. Let \begin{align*}g_n & =\frac{1}{n!}f_n \\ & =\frac{1}{n!} \sum_{k=1}^n (n-k+1) \binom{n}{n-k} a_k \\ & =\sum_{k=1}^n \frac{n-k+1}{(n-k)!} \cdot b_k \end{align*} Therefore \begin{align*}g_{n+1}-g_n & =\sum_{k=1}^{n+1} \frac{n-k+2}{(n+1-k)!} \cdot b_k - \sum_{k=1}^n \frac{n-k+1}{(n-k)!} \cdot b_k \\ & =\sum_{k=2}^{n+1} \frac{n-k+2}{(n+1-k)!} \cdot b_k - \sum_{k=2}^{n+1} \frac{n-k+2}{(n-k+1)!} \cdot b_{k-1} \\ & =\sum_{k=2}^{n+1} \frac{n-k+2}{(n+1-k)!} \cdot (b_k-b_{k-1}). \end{align*} However, if we let $d_n=(-2)^n(b_n-b_{n-1})$, then $d_n=d_{n-1}+\left( 1-\frac{n}{2} \right) \cdot \frac{2^n}{n!}$. So $d_2=2$, $d_n=2+\sum_{i=3}^n \left( 1-\frac{l}{2} \right) \cdot \frac{2^l}{l!}=\frac{2^n}{n!}$. Thus $b_n-b_{n-1}=\frac{d_n}{(-2)^n}=\frac{2^n}{(-2)^n \cdot n!}=\frac{(-1)^n}{n!}$. Therefore \begin{align*} g_{n+1}-g_n & =\sum_{k=2}^{n+1} \frac{n+2-k}{(n+1-k)!} \cdot \frac{(-1)^k}{k!} \\ & =\sum_{k=2}^n \frac{(-1)^k}{(n-k)!k!}+\sum_{k=1}^{n+1} \frac{(-1)^k}{(n+1-k)!k!} \\ & = \frac{1}{n!} \sum_{k=2}^n (-1)^k \binom{n}{k}+\frac{1}{(n+1)!} \sum_{k=2}^{n+1} (-1)^k \binom{n+1}{k}. \end{align*} Since $\sum_{k=0}^n (-1)^k \binom{n}{k}=0$, $\sum_{k=0}^{n+1} (-1)^k \binom{n+1}{k}=0$, So \begin{align*} g_{n+1}-g_n & = -\frac{1}{n!} (1-n)-\frac{1}{(n+1)!}(1-(n+1)) \\ & = \frac{1}{(n-1)!}-\frac{1}{(n+1)!}. \end{align*} Also since $g_3=2b_2+b_3=\frac{4}{3}$, \begin{align*} f_n & =n! g_n \\ &= n! \left( \sum_{k=4}^n \frac{1}{(k-2)!}-\sum_{k=4}^n \frac{1}{k!}+g_3 \right) \\ & = n! \left( g_3+\frac{1}{2!}+\frac{1}{3!}-\frac{n+1}{n!} \right) \\ & = 2 \cdot n!-(n+1) \\ & = 2n!-n-1. \end{align*}
11.07.2017 16:09
This problem can also be solved using combinartorial argument.See a path to combinatorics by T.Andeescu,e.g.,6.10.