Induction Mathematics and Factorials

1.8k Views Asked by At

\usepackage{amsmath}

Evaluate the sum

$\sum_{k=1}^{n} {k\over (k+1)!}$

$\sum_{k=1}^{1} {1\over (1+1)!} = {1\over 2}$

$\sum_{k=1}^{2} {2\over (2+1)!} = {5\over 6}$

$\sum_{k=1}^{3} {3\over (3+1)!} = {23\over 24}$

...

for n = 1, 2, 3, 4 and 5. Make a conjecture about a formula for this sum for general n, and prove your conjecture by mathematical induction.

Conjecture: numerator = denominator - 1

${(k+1)!-1\over (k+1)!} = {k!1!-1\over k!1!} = {k!-1 \over k!} = {k-1\over k}$

This makes sense to me but I'm not sure how to go about writing it in a induction proof format. Is this correct at all? Am I on the right path?

1

There are 1 best solutions below

10
On BEST ANSWER

Your summations following the question are not correct: they should be

$$\begin{align*} \sum_{k=1}^1\frac{k}{(k+1)!}&=\frac1{(1+1)!}=\frac12\\ \sum_{k=1}^2\frac{k}{(k+1)!}&=\frac1{(1+1)!}+\frac2{(2+1)!}=\frac12+\frac26=\frac56\\ \sum_{k=1}^3\frac{k}{(k+1)!}&=\frac56+\frac3{(3+1)!}=\frac56+\frac3{24}=\frac{23}{24}\\ \sum_{k=1}^4\frac{k}{(k+1)!}&=\frac{23}{24}+\frac4{(4+1)!}=\frac{23}{24}+\frac4{120}=\frac{119}{120}\\ \sum_{k=1}^5\frac{k}{(k+1)!}&=\frac{119}{120}+\frac5{(5+1)!}=\frac{119}{120}+\frac5{720}=\frac{719}{720}\;. \end{align*}$$

Be careful not to confuse $k$, the index variable, with $n$, the upper limit of the summation.

The conjecture that

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

is then very reasonable. However, your attempts to simplify it are completely mistaken: you can easily check that in general $(n+1)!\ne n!1!=n!$ and that $\frac{n!-1}{n!}\ne\frac{n-1}n$.

Your next step should be to prove by induction that $(1)$ is true for all $n\ge 1$.

Added: Take $(1)$ as your induction hypothesis; then in the induction step you want to use that hypothesis to prove that

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

Notice that

$$\sum_{k=1}^{n+1}\frac{k}{(k+1)!}=\sum_{k=1}^n\frac{k}{(k+1)!}+\frac{n+1}{(n+2)!}\;;\tag{3}$$

now use $(1)$, your induction hypothesis, to get rid of the summation on the righthand side of $(3)$, and do some algebra to complete the proof of $(2)$.