|
|
| Line 1: |
Line 1: |
| − | For a positive integer <math>n\geq 3</math> plot <math>n</math> equally spaced points around a circle. Label one of them <math>A</math>, and place a marker at <math>A</math>. One may move the marker forward in a clockwise direction to either the next point or the point after that. Hence there are a total of <math>2n</math> distinct moves available; two from each point. Let <math>a_n</math> count the number of ways to advance around the circle exactly twice, beginning and ending at <math>A</math>, without repeating a move. Prove that <math>a_{n-1}+a_n=2^n</math> for all <math>n\geq 4</math>.
| |
| | | | |
| − | == Solution ==
| |
| − | we will use indution and dividing the question to consecutive odds and evens.
| |
| − | we iterate the equality <math>a_{n-1}+a_n=2^n</math>
| |
| − | to <math>n+1</math> to get <cmath>a_n+a_{n+1}=2^{n+1}</cmath>
| |
| − | subtracting the two we get <math>a_n+a_{n+1}-(a_{n-1}+a_n)=2^{n+1}-2^{n}</math>
| |
| − | <cmath>a_{n+1}-a_{n-1}=2^n(2-1)=2^n</cmath>
| |
| − | which is equivalent to <cmath>a_{n+1}a_{n-1}=2^n+a_{n-1}</cmath>
| |
| − | note that for the initial case <math>(n=4)</math>
| |
| − | we have that <math>a_{n-1}=a_{3}</math> has the following moving options:
| |
| − | *<math>2,2,2</math>
| |
| − | *<math>1,2,2,1</math>
| |
| − | *<math>1,1,2,2</math>
| |
| − | *<math>2,2,1,1</math>
| |
| − | *<math>2,1,1,2</math>
| |
| − | (one can easily show that there are no other options)
| |
| − | <center><asy> /* from geogebra: see azjps, userscripts.org/scripts/show/72997 */
| |
| − | import graph; defaultpen(linewidth(0.7)+fontsize(10)); size(100);
| |
| − |
| |
| − | /* segments and figures */
| |
| − | draw(circle((5,0),5));
| |
| − |
| |
| − |
| |
| − | /* points and labels */
| |
| − |
| |
| − | dot((5,5));
| |
| − | dot((9.33,-2.5));
| |
| − | dot((0.66,-2.5));
| |
| − |
| |
| − | clip((-3.72991,-6.47862)--(-3.72991,17.44518)--(32.23039,17.44518)--(32.23039,-6.47862)--cycle);
| |
| − | </asy></center>
| |
| − |
| |
| − | next we show that for <math>n=4</math> <math>a_{n+1}=a_5=2^4+a_3=21</math>
| |
