Problem:
A triangular array of numbers has a first row consisting of the odd integers in increasing order. Each row below the first has one fewer entry than the row above it, and the bottom row has a single entry. Each entry in any row after the top row equals the sum of the two entries diagonally above it in the row immediately above it. How many entries in the array are multiples of ?
Solution:
Note that row is an arithmetic progression with common difference . It can be shown by induction that the first element of row is , and thus the th element of row is , for . For the element to be a multiple of , it must be true that is a multiple of , or that . Multiplying both sides of this congruence by yields , and the fact that and produces . Now in odd-numbered rows, the equations and yield . Note that does not produce any solutions, because row has fewer than entries for . In even-numbered rows, the equations and yield , none of which correspond to entries in the array, so there are no solutions in the even-numbered rows. Thus there are multiples of in the array.
Create a reduced array by dividing each new row by the largest common factor of the elements in the row. The first few rows of this reduced array will be
Note that in row , if , then the elements of row will have the form . If , then the elements of row will have the form . Thus each oddnumbered row consists of the consecutive odd integers from to , and each even-numbered row consists of the consecutive integers from to . Furthermore, because is not divisible by , the entries in the reduced array which are multiples of correspond exactly to the entries in the original array which are multiples of . The additive definition of the array combined with the distributive property of multiplication ensures this. Because all elements of the reduced array are between and , the only elements of the array divisible by are those equal to . All elements of the even-numbered row are at most , so even-numbered rows contain no multiples of , and elements of the oddnumbered row are at most , so the odd-numbered rows up to contain exactly one . Thus the reduced array contains entries equal to , and the original array contains multiples of .
The problems on this page are the property of the MAA's American Mathematics Competitions