# Given $S_n = \sum \dots$ and $a_n = \sum \dots$ prove that $a_n = S_n + {1\over n\cdot n!}$

I'm trying to solve the following problem:

Let: \begin{align} S_n &= 2 + {1\over2!} + {1\over3!} + {1\over 4!} + \dots + {1\over n!} \\ a_n &= 3 - {1\over 1\cdot2\cdot2!} - {1\over 2\cdot3\cdot3!} - \dots - {1\over (n-1)\cdot n\cdot n!} \end{align} Prove that: $$a_n = S_n + {1\over n\cdot n!}$$

My thought on this are:

Manipulating the sums here would become pretty hard so I decided to use another approach. I've tried to look what the first terms of each sum are going to be in order to observe a pattern:

\begin{align} S_1 &= 2 \\ S_2 &= 2 + {1\over 2!} = S_1 + {1\over 2!} \\ S_3 &= 2 + {1\over 2!} + {1\over 3!} = S_2 + {1\over 3!}\\ &\vdots \\ S_{n+1} &= S_n + {1\over (n+1)!} \end{align}

A similar thing is done to $$a_n$$:

$$a_{n+1} = a_n - {1\over n\cdot (n+1) \cdot (n+1)!}$$

So potentially if we could find closed forms of both $$S_n$$ and $$a_n$$ it would become easier to reason about them.

By the way, I've observed both of the sums approach $$e$$ at infinity but from different sides. $$S_n$$ is starting from $$2$$ adding more terms as $$n$$ grows, while $$a_n$$ starts from 3 and decreases the sum as $$n$$ grows. So that will be our initial conditions for both recurrences:

$$S_1 = 2 \\ a_1 = 3$$

The problem just reduced to finding closed forms of the recurrences. Both of them are non-homogenous and here is where I got stuck. Solving for homogenous part is easy since roots of both characteristic equations $$\lambda_{a_n} = \lambda_{S_n} = 1$$.

I couldn't find a particular solution for them. I've tried yet another approach expressing $$S_{n+1}$$ and $$S_{n+2}$$ trying to get rid of the $$1\over (n+1)!$$ or at least change its form so the guess for particular solution is more obvious.

My questions are:

1. Is it even a valid approach to solve the problem?
2. If so then how could I find a closed form for the recurrences? Especially i'm interested in finding a particular solution. (Yet a complete flow is very appreciated and encourages learning by example)
3. Not sure how to phrase that better, but does there exist a table of "guesses" for particular solution of the recurrences in some form of $$x_{n+1} = x_n + F(n)$$. Like if the "free term" is a constant say $$F(n) = 2$$ then the guess for particular solution is some constant $$B$$.

Please excuse me if there is some vagueness or inaccuracy in the terminology, English is not my native language and I have almost no background in Maths.

• It seems unlikely to find a simple closed form, because, as you noticed, the limit converges to $e$. – user600464 Oct 5 '18 at 18:59
• @user600464 is that because $e$ is irrational and that is why no "simple" formula for an irrational number may be obtained? – roman Oct 5 '18 at 19:02
• There is actually a simple formula, the limit $\frac{n^n}{(n- 1)^n}$. However, to compare to this sums, we would need many terms – user600464 Oct 5 '18 at 19:34

## 2 Answers

Personal speaking, you could try your method, but i do not think this is promising. I would prove this by induction instead. For your question 3, you could check this, and you could try these solving techniques but you might go back to the expression given in the problem.

### Proof by induction

$$a_2 - S_2 = 3- 1/4 - (1 + 1/1! + 1/2!)$$ [I think there is some typo in your expression of $$S_n$$] $$= 1/4 = 1/(2 \cdot 2!)]$$. Suppose the equation holds for $$n$$. Then for $$n+1$$, \begin{align*} a_{n+1} - S_{n+1} &= a_n - S_n - \frac 1 {n(n+1) \cdot (n+1)!} - \frac 1{(n+1)!} \\ &= \frac 1 {n!n }-\frac 1 {n(n+1) \cdot (n+1)!} - \frac 1{(n+1)!} \\ &= \frac 1 {(n+1)! (n+1)} \left( \frac {(n+1)^2}n -\frac 1n -(n+1) \right)\\ &= \frac 1 {(n+1)! (n+1)}. \end{align*} Thus the equation holds for all $$n \geqslant 2$$ by induction principle.

\begin{align} \color{red}{a_{n}-S_{n}} &=\left(3-\sum_{k=2}^{n}\frac{1}{(n-1)\cdot n\cdot n!}\right)-\left(2+\sum_{k=2}^{n}\frac{1}{n!}\right) \\[2mm] &=1-\sum_{k=2}^{n}\frac{1}{n!}\left(1+\frac{1}{(n-1)\cdot n}\right) =1-\sum_{k=2}^{n}\frac{1}{n!}\left(1+\frac{1}{n-1}-\frac{1}{n}\right) \\[2mm] &=1-\sum_{k=2}^{n}\frac{1}{n!}\left(\frac{n}{n-1}-\frac{1}{n}\right) =1-\sum_{k=2}^{n}\left(\frac{1}{(n-1)\cdot (n-1)!}-\frac{1}{n\cdot n!}\right) \\[2mm] &=1-\frac{1}{1\cdot1!}+\frac{1}{2\cdot2!}-\frac{1}{2\cdot2!}+\frac{1}{3\cdot3!}-\cdots+\frac{1}{n\cdot n!}=\color{red}{\frac{1}{n\cdot n!}}\quad\left\{\text{telescoping}\right\} \end{align}