5

I've been puzzling over this question for a while now, and I've finally decided to turn to the StackExchange community in order to get an answer.

How would one determine the value of the expression ...5(5+4(4+3(3+2(2+1(1)))))) to n, assuming that in this case n = 5?

Cheers!

Jack D'Aurizio
  • 353,855
MathForTheWin
  • 51
  • 1
    You mean for the rekursive form: $a_1=1$ and $a_{n+1}:=(n+1)\cdot (n+1+a_n)$ find an explizit form? – ctst Nov 10 '16 at 19:23
  • @ctst I'm not sure that's exactly right - seems like it starts at $a_1=0$. But the recurrence appears right. – Thomas Andrews Nov 10 '16 at 19:30
  • 1
    @ThomasAndrews Depending on if you look at the formula in the title or the formula in the text. For the title you are right, for the text I assume I am right :-) – ctst Nov 10 '16 at 19:33
  • 2
    Given the recursion $a_n = n(n+a_{n-1})$ then defining $b_n = a_n / n!$ we get the much simpler recursion $b_n - b_{n-1} = \frac{n^2}{n!}$ which telescopes when summed. – Winther Nov 10 '16 at 19:36

3 Answers3

8

Following Winther and ctst suggestions in the comments, by setting $$ a_1=1,\quad a_{n+1}=(n+1)(n+1+a_n),\quad b_n = \frac{a_n}{n!}\tag{0}$$ we get $b_1=1$ and $b_n-b_{n-1}=\frac{n^2}{n!}=\frac{n}{(n-1)!}$, so: $$ a_n = n!\sum_{k=1}^{n}\frac{(k-1)+1}{(k-1)!}=n!\left(\sum_{k=0}^{n-1}\frac{1}{k!}+\sum_{k=0}^{n-2}\frac{1}{k!}\right)=n!\left(2\sum_{k=0}^{n-1}\frac{1}{k!}-\frac{1}{(n-1)!}\right).\tag{1} $$

Jack D'Aurizio
  • 353,855
6

This can be written as:

$$5\cdot 5 + 5\cdot 4\cdot 4 + 5\cdot 4\cdot 3\cdot3 + 5\cdot 4\cdot 3\cdot 2\cdot 2+5!\cdot 1\\ =\frac{5!}{4!}\cdot 5 + \frac{5!}{3!}\cdot 4 + \frac{5!}{2!}\cdot 3 + \frac{5!}{1!}\cdot 2+\frac{5!}{0!}\cdot 1$$

Then the general formula is:

$$\sum_{k=0}^{n-1}\frac{n!}{k!}(k+1) = n!\sum_{k=0}^{n-1}\frac{k+1}{k!}$$

This likely does not have a closed form, but we can say that:

$$\sum_{k=0}^{n-1}\frac{k+1}{k!} = \frac{1}{(n-1)!}+2\sum_{k=0}^{n-2}\frac{1}{k!} $$

So:

$$\lim_{n\to\infty}\sum_{k=1}^{n-1}\frac{k+1}{k!}=2e$$

Thomas Andrews
  • 177,126
4

Let's start by evaluating the series at small $n$: $$S_1=1^2$$ $$S_2=1^2(2) + 2^2$$ $$S_3=1^2(2)(3) + 2^2(3) + 3^2$$ $$S_4=1^2(2)(3)(4) + 2^2(3)(4) + 3^2(4) + 4^2$$ And generally: $$S_n=1\frac{n!}{0!}+2\frac{n!}{1!}+3\frac{n!}{2!}+...+(n-1)\frac{n!}{(n-2)!}+n\frac{n!}{(n-1)!}$$ $$=\sum_{k=1}^{n} {k\frac{n!}{(k-1)!}}=n!\sum_{k=1}^{n} {\frac{k}{(k-1)!}}=n!\sum_{k=1}^{n} {\frac{1+(k-1)}{(k-1)!}}$$ $$=n!\bigg(\sum_{k=1}^{n} {\frac{1}{(k-1)!}}+\sum_{k=1}^{n}\frac{k-1}{(k-1)!}\bigg)$$ $$=n!\bigg(\sum_{k=1}^{n} {\frac{1}{(k-1)!}}+\sum_{k=2}^{n}\frac{1}{(k-2)!}\bigg)$$ Now we must bring in the identity: $$\sum_{k=1}^{n}{\frac{1}{k!}}=\frac{e\Gamma(n+1,1)}{n!}-1$$ Where $\Gamma(a,b)$ is the incomplete upper gamma function. In this case it can be calculated with the recurrence relation of: $\Gamma(n+1,1)=n\Gamma(n,1)+\frac{1}{e}$

Note: $$\sum_{k=1}^{n} {\frac{1}{(k-1)!}}=\sum_{k=0}^{n-1} {\frac{1}{k!}}=1-\frac{1}{n!}+\sum_{k=1}^{n} {\frac{1}{k!}}=\frac{e\Gamma(n+1,1)-1}{n!}$$ $$\sum_{k=2}^{n} {\frac{1}{(k-2)!}}=\sum_{k=0}^{n-2} {\frac{1}{k!}}=1-\frac{1}{n!}-\frac{1}{(n-1)!}+\sum_{k=1}^{n} {\frac{1}{k!}}=\frac{e\Gamma(n+1,1)-n-1}{n!}$$ Substitute: $$S_n=n!\bigg(\frac{e\Gamma(n+1,1)-1}{n!}+\frac{e\Gamma(n+1,1)-n-1}{n!}\bigg)$$ $$=2e\Gamma(n+1,1)-n-2$$ $$=n(2e\Gamma(n,1)-1)$$ Another evaluation of the upper incomplete gamma function (https://arxiv.org/pdf/math-ph/0501019.pdf) $$\Gamma(n,1)=\frac{1}{e}(1+(n-1)(1+(n-2)(1+(n-3)(1+(n-4)(...)))))$$ This yields: $$S_n=n(1+2(n-1)(1+(n-2)(1+(n-3)(1+(n-4)(...)))))$$ Which isn't really any better than what you started with. There don't seem to be any expressions that can be computed in $O(1)$ time for this sum.