Chapter 25
Some Finite Mathematics
Inductive Proofs & Recursion

Chapter Sections:  [Geometric Sums] [ 25 Arithmetic Sums ] [ 25 Factorial Definition ] [ 25 Product Notation ] [ 25 Notation for Sums ]

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 ¹ 1. Suppose k ³ 0 is a whole number.

Sk = k å j = 0  a Rj = a+aR+aR2+¼aRk-1+aRk

Then

Sk = a· Rk+1-1 R-1

Proof by Mathematical Induction.

If k = 0 then S_k = å_{j = 0}^k a R^j = aR⁰ = a while

a· Rk+1-1 R-1 = a· R0+1-1 R-1 = a·1 = a

Thus the assertion is true for k = 0.

Now we want to show if the assertion

k å j = 1  aRj = a· Rk+1-1 R-1

is true for k = m ³ 0 then it must be true when k = m+1. To this end, suppose

m å j = 1  aRj = a· Rm+1-1 R-1

Therefore

m+1 å j = 1  aRj = aRm+1+ m å j = 1  aRj = aRm+1+a· Rm+1-1 R-1 = a é ê ë Rm+1 R-1 R-1 + Rm+1-1 R-1 ù ú û = a Rm+1(R-1)+ Rm+1-1 R-1 = a Rm+2-Rm+1+ Rm+1-1 R-1 = a R(m+1)-1 R-1

This implies

k å j = 1  aRj = a· Rk+1-1 R-1

when k = m+1. Therefore the principle of mathematical induction implies the result.

Chapter Sections:  [Geometric Sums] [ 25 Arithmetic Sums ] [ 25 Factorial Definition ] [ 25 Product Notation ] [ 25 Notation for Sums ]

Next: 25 Arithmetic Sums or Chapter 26, Proofs and Logic-What's Next

 

Chapters and Appendices

Home
Postscript: The 4-th Skill For Algebra
Foreword
1. Introduction
2. Implication Rules
3. Chains of Reason
4. Romeo and Juliet
4. Induction Mathematical
5 Knowledge Islands
6  Old Language
7  Arith Skill Check
7. The Next Chapters
8 The Three Skills
8 VNR-Concise-Encyclopedia
PS. What is a Variable
9. Algebra Talk
10 Two More Skills
11 Why Shorthand
12 Shorthand Usage
13 What's Next
14 Compound Interest
15 Linear Equations
PS I.  Distributive Law
PS II. Polynomials
16 Painless Proofs
17 Pythagoras
18 Rules of Algebra
19  Functions & Sets
20 Degrees & Radians
21 What's Next
22. Arith & Geometric Sums
23 Summation Notation
24 Your Money
25 Induction & Recursion
26 What's Next
27 Pronouns in Logic
28 Occurrence Tables
29 Contrapositive
30 Truth Tables
31 Indirect Reason
A. Advice For Learning

Words Before Symbols: 
What is a Variable?
Introduction
Variation between Examples
Variation of Letters
A letter denotes a variable
Cases of Double Variation
Three Notions of a Variable
Constants, Parameters
& Variables
Talking about numbers
Dependent or Independent
Variable, a Matter of Choice

www.whyslopes.com   [ Back ] [ Next ] [Top of this Page]

Custom www Search

Road Safety Message  Do not walk on a road with your back to the traffic - rule of thumb Please report by email,  errors in mathematics or grammar or terminology to site author If a mathematics topic you need is not covered in site pages,  report that as well. Topics in most demand will be covered first in site growth.

All trademarks and copyrights on this page are owned by their respective owners.
Copyright to comments & contributions are owned by the Poster. 
The Rest © 1995 onward by site author,   Alan Selby (email form) All Rights Reserved.