9.10.05
The number of ways to tie a necktie using n+2 turns
1, 1, 3, 5, 11, 21, 43, 85, 171...
The Jacobsthal sequence.
I came across this sequence, or originally, double the sequence when I was trying to solve a problem involving counting binary subintervals of the [0, 1] interval. This way of working it out is to add on to each succesive power of 2 the amount by which the previous term falls short of it. Start with 1.
eg.
Here we first subtract the previous (n-1th) term from the 2n-1, then add the result we get back on to 2n-1 to get the nth term. The number we add back on turns out to be the last but one term, illustrating another property of the sequence; that 2 successive terms sum to a power of 2.
An easier way of working it out is to start with 0, double it and then add one (to get 1), double that and _subtract_ 1, (= 1) double and add 1 again (1*2 + 1 = 3), double and subtract 1 (3*2 - 1 = 5) and so on.
If you do something similar, but alternate simple doubling with either doubling and then adding 1, or doubling and subtracting 1, you get the similar sequences 1, 2, 5, 10, 21, 42, 85, 170 (alternately doubling, then doubling and adding 1) and 1, 2, 3, 6, 11, 22, 43, 86, 171 (doubling with doubling and subtracting 1). In the first case every other number is 1 smaller than our original sequence, in the second one every other number is 1 bigger.
Sloane's entry A001045 gives a different recursive definition; a(n) = a(n-1) + 2.a(n-2) (essentially the same as the 1st method above) and lists a huge number of places this sequence occurs, including the one in the title, but doesn't seem to specifically point out that it is the closest integer to 2n/3.
The Jacobsthal sequence.
I came across this sequence, or originally, double the sequence when I was trying to solve a problem involving counting binary subintervals of the [0, 1] interval. This way of working it out is to add on to each succesive power of 2 the amount by which the previous term falls short of it. Start with 1.
eg.
1 1 - 1 = 0 2 - 1 = 1 4 - 3 = 1 8 - 5 = 3 16 - 11 = 5 | 1 + 0 = 1 2 + 1 = 3 4 + 1 = 5 8 + 3 = 11 16 + 5 = 21 |
An easier way of working it out is to start with 0, double it and then add one (to get 1), double that and _subtract_ 1, (= 1) double and add 1 again (1*2 + 1 = 3), double and subtract 1 (3*2 - 1 = 5) and so on.
If you do something similar, but alternate simple doubling with either doubling and then adding 1, or doubling and subtracting 1, you get the similar sequences 1, 2, 5, 10, 21, 42, 85, 170 (alternately doubling, then doubling and adding 1) and 1, 2, 3, 6, 11, 22, 43, 86, 171 (doubling with doubling and subtracting 1). In the first case every other number is 1 smaller than our original sequence, in the second one every other number is 1 bigger.
Sloane's entry A001045 gives a different recursive definition; a(n) = a(n-1) + 2.a(n-2) (essentially the same as the 1st method above) and lists a huge number of places this sequence occurs, including the one in the title, but doesn't seem to specifically point out that it is the closest integer to 2n/3.
# posted by weierstrass @ 14:03 
