Homework 8
Solve the following problems. Justify your answers. Solutions without justification will
not receive full credit.
For the following problems consider the following: write the natural numbers 1 through
n in a circle, start at 1 and cross off every other number until only one number is left. Fo
example, with n = 4 we start at 1, cross off 2, skip 3 and cross off 4, then skip 1 and cross
off 3. Now only the number 1 is left. Let Jn be the number remaining when we start with
numbers 1 through n. So J4 = 1.
(1) Compute Jn by hand for all values 1 ≤ n ≤ 16.
(2) Put the sequence of numbers you generated into the On-Line Encycleopedia of Intege
Sequences. If you’ve done the previous part co
ectly, you should get the entry in OEIS
for this problem.
(3) Write each number 1 through 16 in the following form: 2m + k where m is as large as
possible. For example, 10 = 23 + 2.
(4) Try to guess a formula for Jn based on your answers in parts (1) and (3). You may
use the entry in OEIS to help you here.
(5) Prove that Jn satisfies both of the following recu
ence relations: J2n = 2Jn − 1 and
J2n+1 = 2J2n +1 for n ≥ 1. (Hint: these are two separate cases based on whether there
is an even or odd number of integers written in a circle. What happens if we do one
iteration around the circle of crossing out numbers? Where do we end up? What is
left?)
(6) Use induction and answer in part (5) to prove your guess from part (4). (Hint: You’ll
probably want to do two separate cases based on whether n is even or odd.)
(7) Compute J1000 and J10,000 based on your answer for part (6).
https:
oeis.org
https:
oeis.org/