Question

Suppose that \({a_j} \equiv {b_j}\left( {mod\,m} \right)\) for \(j = 1,\,\,2,...,n\). Use

mathematical induction to prove that

1. \(\sum\limits_{j = 1}^n {{a_j}} \equiv \sum\limits_{j = 1}^n {{b_j}} \left( {mod\,\,m} \right).\)

\(\prod\limits_{j = 1}^n {{a_j}} \equiv \prod\limits_{j = 1}^n {{b_j}} \left( {mod\,\,m} \right).\)

Short answer

1. It is proven that\(\sum\limits_{j = 1}^n {{a_j}} \equiv \sum\limits_{j = 1}^n {{b_j}} \left( {\bmod \,\,m} \right).\)
2. It is proven that \(\prod\limits_{j = 1}^n {{a_j}} \equiv \prod\limits_{j = 1}^n {{b_j}} \left( {\bmod \,\,m} \right).\)

Step-by-step solution

Principle of Mathematical Induction

To prove that\(P\left( n \right)\)is true for all positive integers\(n\), where\(P\left( n \right)\)is a propositional function, we complete two steps:

Basis Step:

We verify that\(P\left( 1 \right)\)is true.

Inductive Step:

We show that the conditional statement \(P\left( k \right) \to P\left( {k + 1} \right)\) is true for all positive integers k.

(a) Proving \(\sum\limits_{j = 1}^n {{a_j}}  \equiv \sum\limits_{j = 1}^n {{b_j}} \left( {mod\,\,m} \right).\)

1. Proving the basis step:

It is given that

\({a_j} \equiv {b_j}\left( {\bmod \,m} \right)\)for\(j = 1,\,\,2,...,n\)

Let,\(P\left( n \right)\): “\(\sum\limits_{j = 1}^n {{a_j}} \equiv \sum\limits_{j = 1}^n {{b_j}} \left( {\bmod \,\,m} \right).\)”

In the basis step, we need to prove that\(P\left( 1 \right)\)is true

For finding statement\(P\left( 1 \right)\)substituting\(1\)for\(n\)in the statement

\({a_1} \equiv {b_1}\left( {\bmod \,m} \right)\)

Which is already given

From the above, we can see that the statement\(P\left( 1 \right)\)is true this is also known as the basis step of the proof.

1. Proving the Inductive step:

In the inductive step, we need to prove that, if\(P\left( k \right)\)is true, then\(P\left( {k + 1} \right)\)is also true.

That is,

\(P\left( k \right) \to P\left( {k + 1} \right)\)is true for all positive integers k.

In the inductive hypothesis, we assume that\(P\left( k \right)\)is true for any arbitrary positive integer\(k\)

That is

\(\sum\limits_{j = 1}^k {{a_j}} \equiv \sum\limits_{j = 1}^k {{b_j}} \left( {\bmod \,\,m} \right).\)

Now we must have to show that\(P\left( {k + 1} \right)\)is also true

Therefore, replacing\(k\)with\(k + 1\)in the statement

\(\sum\limits_{j = 1}^{k + 1} {{a_j}} = {a_{k + 1}} + \sum\limits_{j = 1}^k {{a_j}} \)

Since we know

\({a_{k + 1}} \equiv {b_{k + 1}}\left( {\bmod \,\,m} \right)\)is given

\(\sum\limits_{j = 1}^k {{a_j}} \equiv \sum\limits_{j = 1}^k {{b_j}} \left( {\bmod \,\,m} \right)\)from induction hypothesis

Therefore,

\(\begin{array}{l}\sum\limits_{j = 1}^{k + 1} {{a_j}} \equiv {b_{k + 1}}\left( {\bmod \,\,m} \right) + \sum\limits_{j = 1}^k {{b_j}} \left( {\bmod \,\,m} \right)\\\sum\limits_{j = 1}^{k + 1} {{a_j}} \equiv \sum\limits_{j = 1}^{k + 1} {{b_j}} \left( {\bmod \,\,m} \right)\end{array}\)

From the above, we can see that\(P\left( {k + 1} \right)\)is also true

Hence,\(P\left( {k + 1} \right)\)is true under the assumption that\(P\left( k \right)\)is true. This

completes the inductive step.

Hence It is proven that \(\sum\limits_{j = 1}^n {{a_j}} \equiv \sum\limits_{j = 1}^n {{b_j}} \left( {\bmod \,\,m} \right).\)

(b) Proving \(\prod\limits_{j = 1}^n {{a_j}}  \equiv \prod\limits_{j = 1}^n {{b_j}} \left( {mod\,\,m} \right).\)

1. Proving the basis step:

It is given that

\({a_j} \equiv {b_j}\left( {\bmod \,m} \right)\)for\(j = 1,\,\,2,...,n\)

Let,\(P\left( n \right)\): “\(\prod\limits_{j = 1}^n {{a_j}} \equiv \prod\limits_{j = 1}^n {{b_j}} \left( {\bmod \,\,m} \right).\)”

In the basis step, we need to prove that\(P\left( 1 \right)\)is true

For finding statement\(P\left( 1 \right)\)substituting\(1\)for\(n\)in the statement

\({a_1} \equiv {b_1}\left( {\bmod \,m} \right)\)

Which is already given

From the above, we can see that the statement\(P\left( 1 \right)\)is true this is also known as the basis step of the proof.

1. Proving the Inductive step:

In the inductive step, we need to prove that, if\(P\left( k \right)\)is true, then\(P\left( {k + 1} \right)\)is also true.

That is,

\(P\left( k \right) \to P\left( {k + 1} \right)\)is true for all positive integers k.

In the inductive hypothesis, we assume that\(P\left( k \right)\)is true for any arbitrary positive integer\(k\)

That is

\(\prod\limits_{j = 1}^k {{a_j}} \equiv \prod\limits_{j = 1}^k {{b_j}} \left( {\bmod \,\,m} \right).\)

Now we must have to show that\(P\left( {k + 1} \right)\)is also true

Therefore, replacing\(k\)with\(k + 1\)in the statement

\(\prod\limits_{j = 1}^{k + 1} {{a_j}} = {a_{k + 1}} \cdot \prod\limits_{j = 1}^k {{a_j}} \)

Since we know

\({a_{k + 1}} \equiv {b_{k + 1}}\left( {\bmod \,\,m} \right)\)is given

\(\prod\limits_{j = 1}^k {{a_j}} \equiv \prod\limits_{j = 1}^k {{b_j}} \left( {\bmod \,\,m} \right)\)from induction hypothesis

Therefore,

\(\begin{array}{l}\prod\limits_{j = 1}^{k + 1} {{a_j}} \equiv {b_{k + 1}}\left( {\bmod \,\,m} \right).\prod\limits_{j = 1}^k {{b_j}} \left( {\bmod \,\,m} \right)\\\prod\limits_{j = 1}^{k + 1} {{a_j}} \equiv \prod\limits_{j = 1}^{k + 1} {{b_j}} \left( {\bmod \,\,m} \right)\end{array}\)

From the above, we can see that\(P\left( {k + 1} \right)\)is also true

Hence,\(P\left( {k + 1} \right)\)is true under the assumption that\(P\left( k \right)\)is true. This

completes the inductive step.

Hence It is proven that \(\prod\limits_{j = 1}^n {{a_j}} \equiv \prod\limits_{j = 1}^n {{b_j}} \left( {\bmod \,\,m} \right).\)