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...

See the attachment?


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. For 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 Integer Sequences. If you’ve done the previous part correctly, 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 recurrence 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/