The sequence $(a_{n})$ is defined by $a_1=1$ and $a_n=n(a_1+a_2+\cdots+a_{n-1})$ , $\forall n>1$. (a) Prove that for every even $n$, $a_{n}$ is divisible by $n!$. (b) Find all odd numbers $n$ for the which $a_{n}$ is divisible by $n!$.
Problem
Source: Albanian Mathematical Olympiad 12 GRADE 2011--Question 4
Tags: induction, algebra unsolved, algebra
28.02.2011 14:15
easily it can be proved by induction : $a_{2n}=n.(2n)!$ and $a_{2n+1}=(2n+1)(\frac{(2n+1)!}{2})$
01.03.2011 01:23
The way to discover this is to write $(n+1)a_n = (n+1)n\sum_{k=1}^{n-1} a_k$ $na_{n+1} = n(n+1)\sum_{k=1}^{n} a_k$ Subtracting the two leads to $\dfrac {a_{n+1}} {n+1} = (n+1)\dfrac {a_n} {n} = \cdots = \dfrac {1} {2} (n+1)!$.
06.03.2011 11:43
Well perfectly how Do We Know that $a_n=(\frac{n}{2})n!$ I Mean Without Induction
10.05.2012 18:37
An easy induction shows that $a_n=\frac {n \cdot n!} 2$ for $n>1$. (a) The quotient is $\frac n 2$, which is clearly an integer. (b) The quotient is again $\frac n 2$, which is not an integer, and the only possible value is $n=1$.
23.04.2015 19:18
Cassius wrote: An easy induction shows that $a_n=\frac {n \cdot n!} 2$ for $n>1$. (a) The quotient is $\frac n 2$, which is clearly an integer. (b) The quotient is again $\frac n 2$, which is not an integer, and the only possible value is $n=1$. Can you pls show me the induction steps?
16.04.2017 22:07
sengupta_arka123 wrote: Cassius wrote: An easy induction shows that $a_n=\frac {n \cdot n!} 2$ for $n>1$. (a) The quotient is $\frac n 2$, which is clearly an integer. (b) The quotient is again $\frac n 2$, which is not an integer, and the only possible value is $n=1$. Can you pls show me the induction steps? It can be done even easier without induction, just by noting $a_n = n(a_1+\cdots +a_{n-1}) = n\left(\dfrac{a_{n-1}}{n-1}+a_{n-1}\right)=\dfrac{n^2}{n-1} \cdot a_{n-1}$ for all $n\ge 3$. Then $$a_n = \dfrac{n^2}{n-1} \cdot \dfrac{(n-1)^2}{n-2} \cdots \dfrac{3^2}{2}\cdot a_2 = \dfrac{n\cdot n!}{2}$$and the rest is the same as the above.
31.07.2018 20:15
$a_n=n(a_1+a_2+\cdots+a_n-1)=n\left[(n-1)(a_1+\cdots+a_{n-2})+\cdots \right]$ Take the set $\{1,2,\cdots,n-1\}$. Notice that the products inside the brackets can be any subset of this set, e.g. we can have $(n-1)(n-5)(3)(1)$, or any other product. Let $P_n$ be the sum of the products of the elements in each possible subset. But wait! For $n> 2$ this is just $(1+2)(1+3)(\cdots)(1+n-1)=\frac{n!}{2}$. (If $n\le 2$ then there are no products.) So $a_n=\frac{n!}{2}\cdot n$. (a) As $2\vert n$, $\frac{n}{2}=k$ is an integer so $a_n=k\cdot n!$ (b) We have that $\frac{n}{2}=k$ is not an integer, so $a_n$ is not an integer multiple of $n!$.