Sequences, sums and proof by induction

References

[RS] section 7.2
[SL2] i kompendiet p. 23-28
[SL3] i kompendiet p. 31-35
[HJMT] i kompendiet p. 37-43
Lecture notes parts 8 - 9 (available from course webpage).

Keywords

Sequences: definition by general term and by recurrence relation and initial term(s). Arithmetic and geometric sequences and sums. Sums written in Σ-notation, how to do arithmetic with sums in Σ-notation. A little basic logic. The difference between ⇒ and ⇔. Proof, in particular proof by induction.

Introduction

In this block we shall introduce functions having the positive integers as their domain (sv:definitionsmängd) rather than all of the real numbers. Such functions are known as sequences. We shall see, that apart from the 'normal' way of giving such a function as a rule assigning to each positive integer n in the domain a value f(n), here is a way of giving a sequence in the form of a recurrence relation (sv:rekursionsformel).
Next we consider sums of parts of sequences, and we shall learn a very useful shorthand notation for writing such sums. Σ-notation.
Proving formulas for sums generally involve using a method known as proof by induction (sv: induktionsbevis). We also introduce sufficient logic in order for you to understand the difference between ⇒ and ⇔.

Reading

Sequences and sums

Start by reading part 8 of the lecture notes. These can be found in pdf-format on the course web page. They contain an introduction to sequences, how to give a sequence by recurrence relation and initial term(s) and how to define it by giving a formula for the general term. After an introduction to sequences in general, we discuss arithmetic and geometric sequences and how to find the sum of the first n terms of such sequences. We realise that writing out long sums is a tedious affair, and we thus introduce Σ-notation for sums, and we see how this shorthand notation can actually make it easier to work with sums than if we leave them in the normal long notation. Now read the corresponding sections in [RS] and the kompendium. [RS] section 7.2 contains the introduction to sequences in general and to arithmetic and geometric sequences, [SL2] i kompendiet p. 23-28 contains an introduction to sums and Σ-notation.

Logic and proof

Now read p. 148-155 in part 9 of the lecture notes. These give a short introduction to mathematical statements of the type 'IF p THEN q'. When reading p. 151 and 153 of the lecture notes, try formulating all the statements by using the example where p is the statement x>100 and q is the statement x>10, that is 'IF p THEN q' becomes

IF x>100 THEN x>10.
The most important thing to learn here is the difference between ⇒ and ⇔ and that it is necessary to think every time you write down a line in a solution. You should consider whether the line just follows on from the previous line so that you have an ⇒ between the two lines, or whether the new line also logically implies the previous line so that you have an ⇔ between the two lines. We also revisit equations involving square roots and examine why 'fake roots' sometimes occur when solving equations. Read also [SL3] i kompendiet p. 31-32.

Now read the remainder of part 9 in the lecture notes, these introduce the idea of mathematical proof. Note that p.158-159 in the lecture notes about proof by contradiction are not part of the syllabus of this course, so they won't be examined. They were included so you could see an example of all major kinds of mathematical proof techniques, and because some students asked how to actually prove that the square root of 2 is an irrational number, so I thought I would tell you.

The most important thing to learn here is proof by induction, an important proof technique when you want to prove something for all positive integers. Read also [HJMT] i kompendiet p. 37-43 and [SL3] i kompendiet p. 32-35.

Exercises

Sequences and sums

• [RS] Testproblem 2-3 (on p. 209)


• [SL2ex] p. 46 i kompendiet: uppgift 1, uppgift 2 (solutions on p. 58)


• [RS] Övningar till kapitel 7 p. 224-225:   7.3-7.10

Logical implications

• [DISex] p. 44 i kompendiet: Övning 1.1, 1.2

Proof by induction

• [DISex] p. 45 i kompendiet: uppgift 1.33-1.42