For unlimited access to Class Notes, a Class+ subscription is required.

Review Guide for the Tutorial and Written Quizzes of Lab 5

Part I.Sigma Summation and its Role in Proofs by the Mathematical Induction

In mathematical proofs and scientiﬁc computations it is often necessary to express the sum of a large number of

terms. A convenient method to save time and space is to adopt the sigma notation, using the Greek letter sigma

in its capital form, Σ, to denote summation. Given a ﬁnite set of consecutive integers m, m + 1, . . . , m +p=n,

assign each of these numbers, say, k, to a quantity f(k) that is to be added as a summand in a summation. Then

the sum of these p+ 1 terms, f(m), f(m+ 1),......,f(m+p), may be written as follows

f(m) + f(m+ 1) + · · · · · · +f(n) =

n

P

k=m

f(k),

in which f(k) is referred to as the general term in the summation. The lower limit k=mindicates that the

summation starts with f(m) and the upper limit n(that equals to m+phere) indicates the last term in the

summation is f(n) = f(m+p). So we may read the formula as “the summation of the terms f(k) as kruns from

mto n”.

Some practical rules are summarized below.

(1) Any other symbol may be used to replace kthroughout in the sigma summation, say, f(i) instead of f(k), as

long as the same terms are added. Thus,

n

P

i=m

f(i) =

n

P

k=m

f(k).

(2) It is the same sum if we shift every lable towards the left, or towards the right, by the same distance, and the

expression of the general term changes accordingly. For instance,

n+5

P

k=m+5

f(k−5) =

n

P

k=m

f(k),

because no summand has changed; in particular, the ﬁrst term on the left is still f((m+ 5) −5) = f(m) and the

last term f((n+ 5) −5) = f(n).

(3) A summation may be broken into two summations while two may be merged into one as long as the second

summation starts right after the ﬁrst ends. For instance,

10

P

k=1

f(k) =

4

P

k=1

f(k) +

10

P

k=5

f(k),

5

P

k=0

f(k) +

10

P

k=6

f(k) =

10

P

k=0

f(k) and

n+1

P

k=0

f(k) = f(0) + n

P

k=1

f(k)+f(n+ 1).

(4) The law of distribution of multiplication over addition works well with sigma summation:

n

P

k=1

cf(k) = cn

P

k=1

f(k)

if cis a constant. Also

n

P

k=1

[f(k) + g(k)] = n

P

k=1

f(k)+n

P

k=1

g(k).

All these skills for using the sigma summation are applied in the proof by induction in Example 1 below.

Example 1. Use the Mathematical Induction to prove that, for every integer n≥0,

2n=

n

X

r=0

(−1)rn

r3n−r.

Proof. For n= 0, we verify that

0

P

r=0

(−1)r0

r30−r= (−1)00

030−0= 1 ×1×1 = 1, and also 20= 1.

Assume that the identity holds for some n=k≥0; that is,

2k=

k

X

r=0

(−1)rk

r3k−r.

For n=k+ 1, replace nby k+ 1 in the formula to be proved and get

k+1

P

r=0

(−1)rk+ 1

r3k+1−r

= (−1)0k+ 1

03k+1−0+

k

P

r=1

(−1)rk+ 1

r3k+1−r+ (−1)k+1 k+ 1

k+ 1 3k+1−(k+1)