Question

Use mathematical induction to prove Theorem 1 in Section

4.2, that is, show if bis an integer, where \(b > 1\), and\(n\)is a positive integer, then \(n\)can be expressed uniquely in the form \(n = {a_k}{b^k} + {a_{k - 1}}{b^{k - 1}} + ... + {a_1}b + {a_0}\)

Short answer

Using mathematical induction, It is proved\(n = {a_k}{b^k} + {a_{k - 1}}{b^{k - 1}} + ... + {a_1}b + {a_0}\).

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, it completes two steps:

Basis Step:

it verifies that \(P\left( 1 \right)\)is true.

Inductive Step:

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

Proving the basis step

It is given that,\(b\)is an integer\(b > 1\)and\(0 \le {a_i} < b\),\(i = 0,\,\,1,\,\,2......\).

Let\(P\left( n \right)\): “\(n = {a_k}{b^k} + {a_{k - 1}}{b^{k - 1}} + ... + {a_1}b + {a_0}\)”.

In the basis step, it needs to prove that\(P\left( 1 \right)\)is true.

For finding statement\(P\left( 1 \right)\)substituting\(1\)for\(n\)in the statement\(n = {a_0} = 1\).

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

Proving the Inductive step

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

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

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

That is\(x = {a_k}{b^k} + {a_{k - 1}}{b^{k - 1}} + ... + {a_1}b + {a_0}\).

Now it must have to show that\(P\left( {x + 1} \right)\)is also true.

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

\(x + 1 = {a_{k + 1}}{b^{k + 1}} + {a_k}{b^k} + ... + {a_1}b + {a_0}\)

Now adding\({a_{k + 1}}{b^{k + 1}}\)in induction hypothesis,

\(\begin{aligned}{c}x + {a_{k + 1}}{b^{k + 1}} &= {a_k}{b^k} + {a_{k - 1}}{b^{k - 1}} + ... + {a_1}b + {a_0} + {a_{k + 1}}{b^{k + 1}}\\ &= {a_{k + 1}}{b^{k + 1}} + {a_k}{b^k} + {a_{k - 1}}{b^{k - 1}}... + {a_1}b + {a_0}\\ &= x + 1\end{aligned}\)

From the above, it 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.

Using mathematical induction, it is proved\(n = {a_k}{b^k} + {a_{k - 1}}{b^{k - 1}} + ... + {a_1}b + {a_0}\).