Problem:
Consider the triangular array of numbers with 0,1,2,3,… along the sides and interior numbers obtained by adding the two adjacent numbers in the previous row. Rows 1 through 6 are shown.
Let f(n) denote the sum of the numbers in row n. What is the remainder when f(100) is divided by 100?
Answer Choices:
A. 12
B. 30
C. 50
D. 60
E. 74
Solution:
Calculating the first five values of f,
f(1)=0,f(2)=2,f(3)=6,f(4)=14,f(5)=30
we are led to the conjecture that f(n)=2n−2. We prove this by induction:
Observe that each of the interior numbers in row n is used twice and each of the end numbers is used once as a term in computing the interior terms of row n+1; i.e.,
f(n+1)=[2f(n)−2(n−1)]+2n=2f(n)+2
so if f(n)=2n−2, then f(n+1)=2f(n)+2=2(2n−2)+2=2n+1−2.
Therefore, we seek the remainder when f(100)=2100−2 is divided by 100. Use the fact that 762 has remainder 76 when divided by 100. We find
210​=100K+24,220​=100L+76,240​=100M+76,280​=100N+76,2100​=100Q+76,​
for positive integers K,L,M,N,Q, so f(100)=2100−2 has remander 74 when divided by 100.
.jpg)