## Chapter 5Notes for 22 August

Notes also available as PDF.

### 5.1 The problem solving section is important enough for a full class

• Will dive in on Monday; today is partially review and constructing a bridge to formulas.
• Please read it and look back at the problems we have been solving.
• Think about how the principles apply.
• They may help with the homework.

### 5.2 Review successive differences: a tool for inductive reasoning on sequences

• Problems to find often use inductive reasoning.
• Always take care with your premises. Be sure you understand the framework before exploring with guesses.

Accumulated terminology:

Inductive
making an “educated” guess from prior observations.
Sequence
list of numbers
Term
one of the numbers in a list (in the context of sequences, often used for similar concepts in other contexts)
Arithmetic
Sequence defined by an initial number and a constant increment.
Geometric
Sequence defined by an initial number and a constant multiple.
• Successive differences to reduce a polynomial sequence to an arithmetic one.
• The last column provides the increment.
• To obtain the next term, fill in the table from the right.
• Not useful for geometric sequences; they remain geometric.

Example, text’s problem 4 (not assigned):

 n {A}_{n} {Δ}_{n}^{(1)} = {A}_{n} - {A}_{n-1} {Δ}_{n}^{(2)} = {Δ}_{n}^{(1)} - {Δ}_{n-1}^{(1)} {Δ}_{n}^{(3)} 1 1 2 11 10 3 35 24 14 4 79 44 20 6 5 149 70 26 6 6 251 102 32 6 7 391 140 38 6

### 5.3 Moving from a table to a formula

Some people work better with formulas. The following is not in the text that I can see; this material is extra and meant to be helpful.

Also, this relates inductive and deductive reasoning. The derivation is deductive in breaking down problems and applying rules. But it also is inductive in how we chose to break the problem apart.

### 5.4 Starting point

The goal is

• a formula for {Δ}_{n}^{(1)} .

What do we have?

• The relationships in the successive differences table.
• More specifically, that {Δ}^{(2)} is an arithmetic sequence starting at 14 with an increment of 6.

Extra mathematics and terminology we need include

• symbols for relations ( < is less than, is greater than or equal to) and summations ({Σ}_{k=i}^{j} = i + (i + 1) + \mathop{\mathop{…}} + j);
• properties of arithmetic: commutative, associative, distributive; and
• that a series is the sum of a sequence.

We will prove that

• the formula for {Δ}_{n}^{(1)} is 3{n}^{2} - n = n(3n - 1).

Continuing the same technique would show that

• the formula for {A}_{n} is {n}^{3} + {n}^{2} - 1.

Note that each formula involves {n}^{k} where k is the number of columns to the right.

### 5.5 The plan for deriving a formula

1. Rephrase the problem to include what we know.
2. Express the base sequence {Δ}^{(2)} as a simple formula.
3. Substitute {Δ}^{(2)} into an expression for {Δ}^{(1)}.
4. Break the resulting complicated expression into simpler components.
5. Pull the pieces back together.
6. Check the result.

### 5.6 The derivation

#### 5.6.1 Rephrasing the problem

From the definitions used to form the table we know the following recurrence relationships hold:

\eqalignno{ {Δ}_{n}^{(1)}& = {Δ}_{ n-1}^{(1)} + {Δ}_{ n}^{(2)},\text{ and} & & \cr {Δ}_{n}^{(2)}& = {Δ}_{ n-1}^{(2)} + {Δ}_{ n}^{(3)}. & & }

#### 5.6.2 Expressing the base sequence

{Δ}^{(3)} is a constant sequence for n ≥ 4, so we know that {Δ}^{(2)} is an arithmetic sequence starting with 14 and using 6 as its increment. We can express the nth term as

 {Δ}_{n}^{(2)} = 14 + (n - 3) ⋅ 6\text{ for $n ≥ 3$}

and extend it to the previous entries by defining

 {Δ}_{n}^{(2)} = 0\text{ for $n < 3$}.

(Note: Multiplication is written many ways. Each of a * b = a × b = a ⋅ b = ab are different common forms. The × symbol can be confused with the letter x and is not used often.)

(The term n - 3 shifts n down so the sequence fits our tables. We could have built the table directly across with {Δ}_{n}^{(1)} = {A}_{n+1} - {A}_{n}. Either choice is fine, and this alternative likely work more clearly here.)

#### 5.6.3 Substituting into {Δ}^{(2)} into the expression for {Δ}^{(1)}

Expanding the recurrence for {Δ}_{n}^{(1)} provides

 {Δ}_{n}^{(1)} = 10 + {Σ}_{ k=2}^{n}{Δ}_{ k}^{(2)}\text{ for $n ≥ 2$},

and again we define {Δ}_{n}^{(1)} = 0 for n < 2.

(The expression {Σ}_{k=i}^{j}{x}_{n} denotes the sum of all terms starting at i and ending after j. Σ is a capital Greek S. So {Σ}_{k=1}^{5}i = 1 + 2 + 3 + 4 + 5 = 15.)

Consider only the term {Σ}_{k=2}^{n}{Δ}_{k}^{(2)}. First note that {Δ}_{n}^{(2)} is non-zero only when n ≥ 3, so we can pull out the k = 2 term,

 {Σ}_{k=2}^{n}{Δ}_{ k}^{(2)} = 0 + {Σ}_{ k=3}^{n}{Δ}_{ k}^{(2)}.

Then simplify using 0 + x = x and substitute the expression for {Δ}_{n}^{(2)},

 {Σ}_{k=2}^{n}{Δ}_{ k}^{(2)} = {Σ}_{ k=3}^{n}(14 + 6(k - 3)).

#### 5.6.4 Breaking down the complicated expression

Now we use a few properties of addition and multiplication. We will return to these definitions in later chapters.

• Addition is commutative, a + b = b + a, and associative, (a + b) + c = a + (b + c).
• Multiplication also is commutative, ab = ba, and associative, (ab)c = a(bc).
• Multiplication is the same as repeated adding, so 3x = x + x + x.
• Multiplication is distributive over addition, so ab + ac = a(b + c).

With the associative and commutative properties of addition, we rewrite

 {Σ}_{k=3}^{n}(14 + 6(k - 3)) = ({Σ}_{ k=3}^{n}14) + ({Σ}_{ k=3}^{n}6(k - 3)).

Again, we break the sum apart and work on the pieces. Because multiplication and repeated addition are the same,

 {Σ}_{k=3}^{n}14 = 14 ⋅ ((n - 3) + 1) = 14 ⋅ (n - 2).

There are j - i + 1 terms in the series {Σ}_{k=i}^{j}14. A series is the sum of a sequence.

Applying the distributive property,

 {Σ}_{k=3}^{n}(k - 3) ⋅ 6 = 6 ⋅ {Σ}_{ k=3}^{n}(k - 3),

where we pull out the 6 because it does not depend on the summation variable k. Applying associativity and commutativity again to the {Σ}_{k=3}^{n}(k - 3) term,

 {Σ}_{k=3}^{n}(k - 3) ⋅ 6 = 6 ⋅ (-3(n - 2) + {Σ}_{ k=3}^{n}k).

Consider the term {Σ}_{k=3}^{n}k. We know the sum from 1 to n is n(n + 1)∕2. We present two routes for reducing {Σ}_{k=3}^{n}k to what we already know. The first is to extend the series and subtract the added terms, so

 {Σ}_{k=3}^{n}k = ({Σ}_{ k=1}^{n}k) - {Σ}_{ k=1}^{2}k = n(n + 1)∕2 - 3.

The second shifts the summands to the summation starts at 1. It’s far more complicated but also more general. I won’t cover this during class, but it’s in the notes.

##### The other route, shifting the summation

Our reason for exploring this route is to demonstrate shifting the indices over the summation. To do this, we need to substitute k = i + 2 to reach

 {Σ}_{k=3}^{n}k = {Σ}_{ i+2=3}^{n}(i + 2).

Now remember that the Σ notation implies that we use i + 2 = 3,4,\mathop{\mathop{…}},n. To more the 2 across the equality, we must subtract it from all of the indices, and

 {Σ}_{k=3}^{n}k = {Σ}_{ i+2=3}^{n}(i + 2) = {Σ}_{ i=1}^{n-2}(i + 2).

Now we can separate the terms again and apply {Σ}_{i=1}^{n-2}i = (n - 2)(n - 1)∕2 as well as {Σ}_{i=1}^{n-2}2 = 2(n - 2) to see that

 \begin{array}{lp{10mm}r} \begin{array}{rl} {Σ}_{k=3}^{n}k& = (n - 2)(n - 1)∕2 + 2(n - 2) \\ & = (n - 2)(n - 1 + 4)∕2 \\ & = (n - 2)(n + 3)∕2. \end{array} & \end{array}

This appears to be a different result, but subtracting one expression from the other and expanding results in zero and proves that they are equal.

#### 5.6.5 Pulling the pieces together

To recap, we began with the relationships

\eqalignno{ {Δ}_{n}^{(2)}& = 14 + 6(n - 3)\text{ for $n ≥ 3$, and} & & \cr {Δ}_{n}^{(1)}& = 10 + {Σ}_{ k=2}^{n}{Δ}_{ k}^{(2)}\text{ for $n ≥ 2$.} & & }

Substituting {Δ}_{n}^{(2)} into {Δ}_{n}^{(1)}, regrouping the result and expanding produced many non-trivial subexpressions. Gathering them into one shows

 {Δ}_{n}^{(1)} = 10 + \left (14(n - 2) + 6(-3(n - 2) + n(n + 1)∕2 - 3)\right )\text{ for $n ≥ 2$.}

Simplifying reveals

 {Δ}_{n}^{(1)} = 10 + (3{n}^{2} - n - 10) = 3{n}^{2} - n\text{ for $n ≥ 2$.}

#### 5.6.6 Checking the result

 n {Δ}_{n}^{(1)} 3{n}^{2} - n 1 2 10 12-2 = 10 3 24 27-3 = 24 4 44 48-4 = 44 … … … 10 300-10 = 290

### 5.7 Homework

Practice is absolutely critical in this class.

Groups are fine, turn in your own work. Homework is due in or before class on Mondays.

• Exercises for Section 1.2:
• Problem 49. Working inductively here is far simpler than deriving the formula.
• Problems 51, 54. Try both inductively and by playing with the formula.

Note that you may email homework. However, I don’t use MicrosoftTM products (e.g. Word), and software packages are notoriously finicky about translating mathematics.

If you’re typing it (which I advise just for practice in whatever tools you use), you likely want to turn in a printout. If you do want to email your submission, please produce a PDF or PostScript document.