MA121 Lecture 1: MA121-Lab4

74 views4 pages
11 Feb 2019
School
Department
Course
Professor

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(k5) =
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 n0,
2n=
n
X
r=0
(1)rn
r3nr.
Proof. For n= 0, we verify that
0
P
r=0
(1)r0
r30r= (1)00
0300= 1 ×1×1 = 1, and also 20= 1.
Assume that the identity holds for some n=k0; that is,
2k=
k
X
r=0
(1)rk
r3kr.
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+1r
= (1)0k+ 1
03k+10+
k
P
r=1
(1)rk+ 1
r3k+1r+ (1)k+1 k+ 1
k+ 1 3k+1(k+1)
Unlock document

This preview shows page 1 of the document.
Unlock all 4 pages and 3 million more documents.

Get access

\$10 USD/m
Billed \$120 USD annually
Homework Help
Class Notes
Textbook Notes