Accumulated terminology:
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 |
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.
The goal is
What do we have?
Extra mathematics and terminology we need include
We will prove that
Continuing the same technique would show that
Note that each formula involves {n}^{k} where k is the number of columns to the right.
From the definitions used to form the table we know the following recurrence relationships hold:
{Δ}^{(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.)
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)).
|
Now we use a few properties of addition and multiplication. We will return to these definitions in later chapters.
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.
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.
To recap, we began with the relationships
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$.}
|
| 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 | |
Practice is absolutely critical in this class.
Groups are fine, turn in your own work. Homework is due in or before class on Mondays.
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.