Answer to Question #231394 in Discrete Mathematics for citra

Question

Find a formula for

1+1+⋯+ 1

1 ⋅ 2 2 ⋅ 3 n(n + 1)

by examining the values of this expression for small

values of n.

b) Prove the formula you conjectured in part

Answer 1

a)

$1+1+...+1=\displaystyle\sum_{i=1}^n1=n$

$\dfrac{1}{1\cdot2}+\dfrac{1}{2\cdot3}+...+\dfrac{1}{n(n+1)}=\displaystyle\sum_{i=1}^n\dfrac{1}{n(n+1)}=\dfrac{n}{n+1}$

b) Let $P(n)$ be the proposition that $1+1+...+1=\displaystyle\sum_{i=1}^n1,$ is $n.$ We must prove that $P(n)$ is true for $n=1,2,3,...$

BASIS STEP: $P(1)$ is true, because $1=\displaystyle\sum_{i=1}^11=1.$

INDUCTIVE STEP: For the inductive hypothesis we assume that $P(k)$ holds for an arbitrary positive integer $k.$ That is, we assume that

$1+1+...+1=\displaystyle\sum_{i=1}^k1=k$

Under this assumption, it must be shown that $P(k+1)$ is true, namely, that

$1+1+...+1=\displaystyle\sum_{i=1}^{k+1}1=k+1$

is also true.

When we add $1$ to both sides of the equation in $P(k),$ we obtain

$\displaystyle\sum_{i=1}^k1+1=\displaystyle\sum_{i=1}^{k+1}1=k+1$

This last equation shows that $P(k+1)$ is true under the assumption that $P(k)$ is true. This completes the inductive step.

We have completed the basis step and the inductive step, so by mathematical induction we know that $P(n)$ is true for all positive integers $n.$ That is, we have proven that

$1+1+...+1=\displaystyle\sum_{i=1}^n1=n$

for all positive integers $n.$

Let $P(n)$ be the proposition that $\dfrac{1}{1\cdot2}+\dfrac{1}{2\cdot3}+...+\dfrac{1}{n(n+1)}=\displaystyle\sum_{i=1}^n\dfrac{1}{n(n+1)}$ is $\dfrac{n}{n+1}.$ We must prove that $P(n)$ is true for $n=1,2,3,...$

BASIS STEP: $P(1)$ is true, because $\dfrac{1}{1\cdot2}=\displaystyle\sum_{i=1}^1\dfrac{1}{n(n+1)}=\dfrac{1}{1+1}=\dfrac{1}{2}.$

INDUCTIVE STEP: For the inductive hypothesis we assume that $P(k)$ holds for an arbitrary positive integer $k.$ That is, we assume that

$\dfrac{1}{1\cdot2}+\dfrac{1}{2\cdot3}+...+\dfrac{1}{k(k+1)}=\displaystyle\sum_{i=1}^k\dfrac{1}{k(k+1)}=\dfrac{k}{k+1}$

Under this assumption, it must be shown that $P(k+1)$ is true, namely, that

$\dfrac{1}{1\cdot2}+\dfrac{1}{2\cdot3}+...+\dfrac{1}{k(k+1)}+\dfrac{1}{(k+1)(k+1+1)}$ $=\displaystyle\sum_{i=1}^{k+1}\dfrac{1}{k(k+1)}=\dfrac{k+1}{k+1+1}$

is also true.

When we add $\dfrac{1}{(k+1)(k+1+1)}$ to both sides of the equation in $P(k),$ we obtain

$\displaystyle\sum_{i=1}^k\dfrac{1}{k(k+1)}+\dfrac{1}{(k+1)(k+1+1)}=\displaystyle\sum_{i=1}^{k+1}\dfrac{1}{k(k+1)}$ $=\displaystyle\sum_{i=1}^{k+1}\dfrac{1}{k(k+1)}=\dfrac{k}{k+1}+\dfrac{1}{(k+1)(k+1+1)}$

$=\dfrac{k(k+2)+1}{(k+1)(k+2)}=\dfrac{(k+1)^2}{(k+1)(k+2)}$

$=\dfrac{k+1}{k+2}=\dfrac{k+1}{k+1+1}$

This last equation shows that $P(k+1)$ is true under the assumption that $P(k)$ is true. This completes the inductive step.

We have completed the basis step and the inductive step, so by mathematical induction we know that $P(n)$ is true for all positive integers $n.$ That is, we have proven that

$\dfrac{1}{1\cdot2}+\dfrac{1}{2\cdot3}+...+\dfrac{1}{n(n+1)}=\displaystyle\sum_{i=1}^n\dfrac{1}{n(n+1)}=\dfrac{n}{n+1}$

for all positive integers $n.$