Chapter 25
Some Finite Mathematics
Inductive Proofs & Recursion

Volume 2, Three Skills for Algebra

The chapter Longer Chains of Reason described mathematical induction. It is a method of proof, which relied on a sequence of assertions, each one of which implied that it successor == the next one in the sequence.

Mathematical induction is used in the first section to confirm or justify the addition formulas given earlier for geometric and arithmetic sums, and to say a little more. The proofs in this chapter may look intimidating at first, but once the first proof is done, the rest are similar.

• The second section talks about recursion. Recursion is based on the idea that as soon as one calculation is done, a next may be also be done.

1  Proof by Mathematical Induction

First Example

In this chapter we revisit the treatment of geometric and arithmetic sums given earlier. Mathematical induction is employed to justify the earlier formulas for the values of these sums. The next chapter is easier to read. (Help may be required with this chapter.)

Theorem 25.1 [On Geometric Sums] Suppose $a$ and $R$ are real numbers with $R\ne1$. Suppose $k\ge0$ is a whole number. \[S_k=\sum_{j=0}^k a R^j =a+aR+aR^2+\cdots aR^{k-1}+aR^k \] Then \[S_k= a\cdot \frac {R^{k+1}-1}{R-1} \]

Proof by Mathematical Induction.

If $k=0$ then $S_k=\sum_{j=0}^k a R^j= aR^0=a$ while \[a\cdot \frac {R^{k+1}-1}{R-1}=a\cdot \frac {R^{0+1}-1}{R-1}=a\cdot 1=a\] Thus the assertion is true for $k=0$.

Now we want to show if the assertion \[\sum_{j=1}^k aR^j=a\cdot \frac {R^{k+1}-1}{R-1}\] is true for $k=m\ge0$ then it must be true when $k=m+1$.

> To this end, suppose \[\sum_{j=1}^m aR^j=a\cdot \frac {R^{m+1}-1}{R-1}\] Therefore \begin{eqnarray*} \sum_{j=1}^{m+1}aR^j&=&aR^{m+1}+\sum_{j=1}^m aR^j \\ & =&aR^{m+1}+a\cdot \frac {R^{m+1}-1}{R-1}\\ & =&a\left[R^{m+1}\frac{R-1}{R-1}+ \frac{R^{m+1}-1}{R-1}\right] \\ & =&a\frac{R^{m+1}({R-1})+ R^{m+1}-1}{R-1}\\ & =&a\frac{R^{m+2}-R^{m+1}+ R^{m+1}-1}{R-1}\\ & =&a\frac{R^{(m+1)-1}}{R-1} \end{eqnarray*}

This implies \[\sum_{j=1}^k aR^j=a\cdot \frac {R^{k+1}-1}{R-1}\] when $k=m+1$.

Therefore the principle of mathematical induction implies the result.

---

Mathematical Induction Second Example - Arithmetic Sums

We revisit the treatment of geometric and arithmetic sums given earlier. Mathematical induction is employed to justify the earlier formulas for the values of these sums. The next chapter is easier to read. (Help may be required with this chapter.)

Theorem 25.2 [On Sume of Arithmetic Sequences]

Suppose $c_{k+1}=c_k+a$ for $k=1\dots,n-1$. Suppose \[S_m= \sum_{j=1}^mc_j=c_1+c_2+\cdots +c_m\] whenever $1\le m \le n$.

Then (i) for $k=1\dots,n$ \[c_k=c_1+(k-1)\] Further (ii) for $k=1\dots,n$, \[S_k= \sum_{j=1}^kc_j=kc_1+\frac12k(k-1)\] and also (iii) \[S_k= \sum_{j=1}^kc_j=\frac12k(c_1+c_k)\]

Note (iii) says that $2S_k$ is $k$ times the sum of the first and last terms. The following proofs are optional readings in the first instance, but it mastery no matter how slowly will give you a taste hopefully not too bitter of higher mathematics.

>

2. Factorial Function

Inductive Proofs & Recursion

The recursive computation (or definition) of formulas f(n) refers to the idea that f(n) can be computed once f(n-1) and/or previous values of  f(j) have been computed.

Product of Odd Numbers

First, we will begin will an example. Put P₁ = 1. Then for n ³ 1, suppose P_n+1 = P_n·(2n+1). This successively implies that

Exercise:   Compute P₂,P₃,P₅,P₈ and P₉, or obtain formulas for them which involves numbers and no shorthand notation.

2.3  Product Notation

If $a_j=f(j)$ for some function $f(j)$ of whole numbers $j\ge1$, we may put \[ \Pi_{j=1}^1 a_j=a_1 \] and then once $\Pi_{j=1}^{n} a_j$ is calculated, put \[ \Pi_{j=1}^{n+1} a_j=a_{n+1}\cdot\left(\Pi_{j=1}^n a_j \right) \] This implies that $\Pi_{j=1}^n a_j$ is the product of the numbers \[a_1, a_2, a_3, \ldots, a_n\] That is, \[ \Pi_{j=1}^n a_j= a_1\cdot a_2 \cdots a_n \] Now $n!=\Pi_{j=1}^n j$. Further the product of the first $n$ odd numbers $P_n=\Pi_{j=1}^n (2j+1)$. The product $P=\Pi_{j=1}^n a_j$ is similar to the sum $S=\sum^n_{j=1}a_j$, but with the use of multiplication instead of addition. The product $P$ and the sum $S$ represent of course, different computations.

Summation Notation

Saying how to compute a number gives a definition of it. Since a single number may be computed in several different ways, it may have several equivalent definitions.

The shorthand notation

\[\sum_{j=m}^k f(j)\]

more generally has the following two properties

\begin{eqnarray*} \sum_{j=m}^m f(j)&=&f(m) \\ \sum_{j=m}^{k+1} f(j)&=&f(k+1)+\sum_{j=m}^k f(j) \end{eqnarray*}

whenever $k=m,m+1,m+2,m+3,m+4 \ldots $ is a whole number $\ge m$. The latter says that once \[\sum_{j=m}^k f(j)\] has been or is computed, the value of

\[\sum_{j=m}^{k+1} f(j)\]

can be obtained by adding $f(k+1)$. This describes the recursive or inductive computation (or definition) of \[S(n,m)=\sum_{j=m}^n f(j)\] for whole or integers numbers $n\ge m$. The two cases where the initial or lower index $m=0$ has value or value $m=1$ occur often in examples. But other cases can occur, and eventually do.

Remark - May 1, 2012: The phrases recursive definition and inductive definition are interchangeable in mathematics.

Arithmetic - Ages 10+
1. Deciml Place Value - fun
2. Decimals for Tutors
3. Prime Factors - quickly
4. Fractions + Ratios
5. Arith with units - science