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.$