Question

DISCRETE STRUCTURES

1. Prove the following formulas for all positive integers n.
a) 1 + 2 + 3 + 4 + 5 +...+ n = n(n + 1) :2
b) 1 + 4 + 9 + 16 + 25 + ...+ n2 = n(n + 1)(2n + 1) :6
c) 22n - 1 is a multiple of 3

Answer 1

ANSWER on Question #76221 – Math – Discrete Mathematics

QUESTION

Prove the following formulas for all positive integers $n$.

a) $1 + 2 + 3 + 4 + 5 + \ldots + n = \frac{n(n + 1)}{2}$

b) $1 + 4 + 9 + 16 + 25 + \ldots + n^2 = \frac{n(n + 1)(2n + 1)}{6}$

c) $2^{2n} - 1$ is a multiple of 3

SOLUTION

All formulas will be proved by using the method of mathematical induction.

(More information: https://en.wikipedia.org/wiki/Mathematical_induction)

a)

$$1 + 2 + 3 + 4 + 5 + \ldots + n = \frac{n(n + 1)}{2}$$

1 STEP: Basis of induction

We verify the validity of the formula for $n = 1$

$$\text{for } n = 1: 1 + 2 + 3 + 4 + 5 + \cdots + n = 1$$ $$\text{for } n = 1: \frac{n(n + 1)}{2} = \frac{1 \cdot (1 + 1)}{2} = \frac{1 \cdot 2}{2} = 1$$

Conclusion,

$$\left\{ \begin{array}{c} \text{for } n = 1: 1 + 2 + 3 + 4 + 5 + \cdots + n = 1 \\ \text{for } n = 1: \frac{n(n + 1)}{2} = 1 \end{array} \right. \to$$ $$1 + 2 + 3 + 4 + 5 + \ldots + n = \frac{n(n + 1)}{2}, \text{ for } n = 1$$

2 STEP: Inductive hypothesis

The formula is true for $1 \leq k \leq n$

$$1 + 2 + 3 + 4 + 5 + \dots + k = \frac {k (k + 1)}{2}$$

3 STEP: The inductive step

It is necessary to prove that for $k = n + 1$

$$1 + 2 + 3 + 4 + 5 + \dots + (n + 1) = \frac {(n + 1) (n + 2)}{2}$$

In our case,

$$\begin{array}{l} 1 + 2 + 3 + 4 + 5 + \dots + (n + 1) = \underbrace {(1 + 2 + 3 + 4 + 5 + \cdots + n)} _ {\frac {n (n + 1)}{2}} + (n + 1) = \\ = \frac {n (n + 1)}{2} + \frac {(n + 1) ^ {\backslash 2}}{1} = \frac {n (n + 1)}{2} + \frac {2 (n + 1)}{2} = \frac {n (n + 1) + 2 (n + 1)}{2} = \frac {(n + 1) (n + 2)}{2} \end{array}$$

Conclusion,

$$1 + 2 + 3 + 4 + 5 + \dots + (n + 1) = \frac {(n + 1) (n + 2)}{2}$$

Q.E.D.

b)

$$1 + 4 + 9 + 16 + 25 + \dots + n ^ {2} = \frac {n (n + 1) (2 n + 1)}{6}$$

1 STEP: Basis of induction

We verify the validity of the formula for $n = 1$

$$f o r n = 1: 1 + 4 + 9 + 16 + 25 + \dots + n ^ {2} = 1 ^ {2} = 1$$ $$f o r n = 1: \frac {n (n + 1) (2 n + 1)}{6} = \frac {1 \cdot (1 + 1) \cdot (2 \cdot 1 + 1)}{6} = \frac {1 \cdot 2 \cdot 3}{6} = 1$$

Conclusion,

$$\left\{ \begin{array}{c} f o r n = 1: 1 + 4 + 9 + 16 + 25 + \dots + n ^ {2} = 1 \\ f o r n = 1:: \frac {n (n + 1) (2 n + 1)}{6} = 1 \end{array} \right. \to$$ $$1 + 4 + 9 + 16 + 25 + \dots + n ^ {2} = \frac {n (n + 1) (2 n + 1)}{6}, f o r n = 1$$

2 STEP: Inductive hypothesis

The formula is true for $1 \leq k \leq n$

$$1 + 4 + 9 + 16 + 25 + \dots + k ^ {2} = \frac {k (k + 1) (2 k + 1)}{6}$$

3 STEP: The inductive step

It is necessary to prove that for $k = n + 1$

$$1 + 4 + 9 + 16 + 25 + \dots + (n + 1) ^ {2} = \frac {(n + 1) (n + 2) (2 (n + 1) + 1)}{6}$$

In our case,

$$\begin{array}{l} 1 + 4 + 9 + 16 + 25 + \dots + (n + 1) ^ {2} = \underbrace {(1 + 4 + 9 + 16 + 25 + \cdots + n ^ {2})} _ {\frac {n (n + 1) (2 n + 1)}{6}} + (n + 1) ^ {2} = \\ = \frac {n (n + 1) (2 n + 1)}{6} + \frac {(n + 1) ^ {2}}{1} ^ {\backslash 6} = \frac {n (n + 1) (2 n + 1)}{6} + \frac {6 (n + 1) ^ {2}}{6} = \\ = \frac {n (n + 1) (2 n + 1) + 6 (n + 1) ^ {2}}{6} = \frac {(n + 1) \left(n (2 n + 1) + 6 (n + 1)\right)}{6} = \\ = \frac {(n + 1) (2 n ^ {2} + n + 6 n + 6)}{6} = \frac {(n + 1) (2 n ^ {2} + 7 n + 6)}{6} = \frac {(n + 1) (2 n ^ {2} + 3 n + 4 n + 6)}{6} = \\ = \frac {(n + 1) (n (2 n + 3) + 2 (2 n + 3))}{6} = \frac {(n + 1) (2 n + 3) (n + 2)}{6} = \\ \end{array}$$ $$= \frac{(n + 1)(n + 2)(2(n + 1) + 1)}{6}$$

Conclusion,

$$1 + 4 + 9 + 16 + 25 + \cdots + (n + 1)^2 = \frac{(n + 1)(n + 2)(2(n + 1) + 1)}{6}$$

Q.E.D.

c)

$$2^{2n} - 1 \text{ is a multiple of } 3$$

1 STEP: Basis of induction

We verify the validity of the formula for $n = 1$

$$\text{for } n = 1 : 2^{2 \cdot 1} - 1 = 2^2 - 1 = 4 - 1 = 3 \text{ is a multiple of } 3$$

Conclusion,

$$2^{2n} - 1 \text{ is a multiple of } 3, \text{ for } n = 1$$

2 STEP: Inductive hypothesis

The formula is true for $1 \leq k \leq n$

$$2^{2k} - 1 \text{ is a multiple of } 3$$

3 STEP: The inductive step

It is necessary to prove that for $k = n + 1$

$$2^{2(n + 1)} - 1 \text{ is a multiple of } 3$$

In our case,

$$\begin{array}{l} 2^{2(n + 1)} - 1 = 2^{2n + 2} - 1 = 2^{2n} \cdot 2^2 - 1 = 2^{2n} \cdot 4 - 1 = 2^{2n} \cdot (3 + 1) - 1 = \\ = 3 \cdot 2^{2n} + (2^{2n} - 1) \end{array}$$

Conclusion,

$$2^{2(n+1)} - 1 = 3 \cdot 2^{2n} + (2^{2n} - 1)$$

$\left\{ \begin{array}{l} 3 \cdot 2^{2n} \text{ is a multiple of } 3, \text{ because there is the factor } 3 \\ 2^{2n} - 1 \text{ is a multiple of } 3, \text{ by the inductive hypothesis} \end{array} \right.$ →

If each term is divisible by 3, then the sum is divisible by 3

$$2^{2(n+1)} - 1 = 3 \cdot 2^{2n} + (2^{2n} - 1) \text{ is a multiple of } 3$$

Q.E.D.

Answer provided by https://www.AssignmentExpert.com