Quite hard !!! (may be)

For discussing Olympiad Level Combinatorics problems
User avatar
sm.joty
Posts:327
Joined:Thu Aug 18, 2011 12:42 am
Location:Dhaka
Quite hard !!! (may be)

Unread post by sm.joty » Sun Aug 26, 2012 11:15 pm

Show that for $n \in \mathbb{N}$,
$\displaystyle\sum_ {k = 0}^{n} n \mathrm{P}_k = \left\lfloor{n!e}\right\rfloor $

Source: The Collage Math J.20(1989),260
:ugeek:
হার জিত চিরদিন থাকবেই
তবুও এগিয়ে যেতে হবে.........
বাধা-বিঘ্ন না পেরিয়ে
বড় হয়েছে কে কবে.........

User avatar
SANZEED
Posts:550
Joined:Wed Dec 28, 2011 6:45 pm
Location:Mymensingh, Bangladesh

Re: Quite hard !!! (may be)

Unread post by SANZEED » Tue Aug 28, 2012 12:12 am

$n!e=n!(1+\frac{1}{2!}+\frac{1}{3!}+...)=(\displaystyle\sum_{k=0}^{n}\frac{n!}{(n-k)!})+\frac{n!}{(n+1)!}+\frac{n!}{(n+2)!}+...$
All we have got to do next is to show that $\frac{n!}{(n+1)!}+\frac{n!}{(n+2)!}+...=\frac{1}{n+1}+\frac{1}{(n+1)(n+2)}...<1$.
Can we do that?
Last edited by SANZEED on Tue Aug 28, 2012 12:59 am, edited 1 time in total.
$\color{blue}{\textit{To}} \color{red}{\textit{ problems }} \color{blue}{\textit{I am encountering with-}} \color{green}{\textit{AVADA KEDAVRA!}}$

User avatar
sm.joty
Posts:327
Joined:Thu Aug 18, 2011 12:42 am
Location:Dhaka

Re: Quite hard !!! (may be)

Unread post by sm.joty » Tue Aug 28, 2012 12:30 am

SANZEED wrote:$n!e=n!(1+\frac{1}{2!}+\frac{1}{3!}+...)=(\displaystyle\sum_{k=0}^{n}\frac{n!}{(n-k)!})+\frac{n!}{(n+1)!}+\frac{n!}{(n+2)!}+...$
All we have got to do next is to show that $\frac{n!}{(n+1)!}+\frac{n!}{(n+2)!}+...=\frac{1}{n+1}+\frac{1}{n+2}...<1$.
Can we do that?
may be here is a typo (i'm not sure :( )
$ \displaystyle\sum_{k=0}^{n}\frac{n!}{(n-k)!})$+$\frac{n!}{(n+1)!}+\frac{n!}{(n+2)!}+... $
হার জিত চিরদিন থাকবেই
তবুও এগিয়ে যেতে হবে.........
বাধা-বিঘ্ন না পেরিয়ে
বড় হয়েছে কে কবে.........

User avatar
SANZEED
Posts:550
Joined:Wed Dec 28, 2011 6:45 pm
Location:Mymensingh, Bangladesh

Re: Quite hard !!! (may be)

Unread post by SANZEED » Tue Aug 28, 2012 12:33 am

Nope mine's correct.Because $n!(1+\frac{1}{2!}+...)=n!+\frac{n!}{2!}+...+\frac{n!}{n!}+\frac{n!}{(n+1)!}+...=\displaystyle\sum_{k=0}^{n}\frac{n!}{(n-k)!}+\frac{n!}{(n+1)!}+...$.
$\color{blue}{\textit{To}} \color{red}{\textit{ problems }} \color{blue}{\textit{I am encountering with-}} \color{green}{\textit{AVADA KEDAVRA!}}$

User avatar
SANZEED
Posts:550
Joined:Wed Dec 28, 2011 6:45 pm
Location:Mymensingh, Bangladesh

Re: Quite hard !!! (may be)

Unread post by SANZEED » Wed Aug 29, 2012 11:55 pm

Alright.I think this will work.Thanks to Nacho Darago from Argentina for helping me. Let us assume that $f(n,k)=\frac{1}{(n+1)...(n+k)}$ and define $S(n,k)=\displaystyle\sum_{i=1}^{k}f(n,k)$. Now we use induction to show that $S(n,k)<1-\frac{1}{k+1}$. That clearly finishes the problem.The steps are as follows:
:arrow: The base cases are $k=1,2$ which can be proved with calculation.
:arrow: Now let us assume that for certain $k$,$S(n,k)<1-\frac{1}{k+1}$
:arrow: Now we add the term $\frac{1}{(n+1)...(n+k)(n+k+1)}$ on each side. It suffices to prove that $S(n,k+1)<1-\frac{1}{k+2}$. now, calculation yields that it is equivalent to prove that $f(n,k+1)<\frac{1}{k+1}-\frac{1}{k+2}$
Now we can apply induction here too,the base cases can be done easily. Assume that $f(n,k)<\frac{1}{k}-\frac{1}{k+1}$. Now $f(n,k+1)=\frac{f(n,k)}{n+k+1}$. Now a little calculation says that it is equivalent to prove that $1+\frac{2}{k}<n+k+1$ which is obvious.
I hope I am correct throughout my solution. :|
$\color{blue}{\textit{To}} \color{red}{\textit{ problems }} \color{blue}{\textit{I am encountering with-}} \color{green}{\textit{AVADA KEDAVRA!}}$

Post Reply