CPSC 121 Assignment 4 Solutions 2021

CPSC 121


[8 marks] Prove that for every three non-zero integers a, b and c, at least one of the
three products ab, ac, bc is positive. Hint: use a proof by contradiction.
Proof (by contradiction):
Consider unspecified non-zero integers a, b, c. For the purpose of contradiction, assume
that none of the three products ab, ac, bc are positive. In other words, assume that all
three products are negative.
Consider the product ab. Since ab is negative, assume WLOG that a is positive and b is
negative. Since a is positive and ac is negative, then c is negative.
Since bc is negative, then exactly one of b or c must be negative. This contradicts with
our observation that both b and c must be negative. Therefore, our original assumption
is false, and for every three non-zero integers a, b and c, at least one of the three products
ab, ac, and bc is positive.

, CPSC 121


[8 marks] The Fibonacci numbers are defined as follows: F0 = F1 = 1 and for every
i ≥ 2, Fi = Fi−1 + Fi−2 . We thus get the sequence

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, . . .

Prove by induction that
n
X
Fi = Fn+2 − 1
i=0

Proof by weak induction on n:



Base case: for n = 0
X0
F (i) = F (0) = 1
i=0
0
X
F (i) = F (0 + 2) − 1 = F (2) − 1 = 2 − 1 = 1
i=0
The theorem holds for n = 0.



Inductive hypothesis:
n−1
X
Fi = Fn−1+2 − 1 = Fn+1 − 1
i=0




Inductive step:
Consider an unspecified natural number n. Assume n ≥ 1.
n
X n−1
X
Fi = Fi + Fn by definition of the sum
i=0 i=0
= Fn+1 − 1 + Fn by IH
= Fn+2 − 1 by the Fibonacci definition Fn+2 = Fn + Fn+1
X n
Therefore, by the principle of mathematical induction, Fi = Fn+2 − 1.
i=0