Define the sequence a1, a2, a3, ... by 2n = the sum of ad such that d divides n. Show that an is divisible by n. [For example, a1 = 2, a2 = 2, a3 = 6.]
Solution
Let bn be the number of sequences of length n, made up of 0s and 1s, which cannot be divided into more than one identical block. Then bn satisfies the same recurrence relation as an and has the same initial values. So they are the same. But bn must be divisible by n, because we can divide the non-repeating sequences of length n into groups of n, where the sequences in each group are obtained from each other by cyclic shifts.
© John Scholes
jscholes@kalva.demon.co.uk
28 Dec 2002
Last corrected/updated 28 Dec 02