Page 92 - 'Blast_Into_Math

Blast into Math! The Euclidean algorithm: a computational recipe

So, the base case is true. Then, you assume the equation is true for n , and show that it is then
also true for n +1. For n +1, the product looks like

n+1
1
1+ .
k
k=1

Think about the following

n +2 1
n
1+ .
n +1 k
k=1

What is this? Don’t forget to use the induction assumption.

• Hint for # 9: Imagine that factorials are like onions, where all the integers multiplied
together are like the layers of the onion. When you divide one factorial by another, it’s like
removing layers of the onion. What is

n+k

n! j
j=n+1

equal? (Hint: It’s equal to some factorial.)

1 100
9 9
8 8
7 7
6 6
5 5 1 100
9 9 8 8 7 7
4 4 33 22 11
= = 6 6
/

/ 55
4 4 33 22 11

• Hint for # 10: Let’s call the the four positive integers a , b , c and d . Now, let’s think about
all possible sets of three of them. There are four such sets

{a, b, c}, {a, c, d}, {a, b, d}, {b, c, d}.

92