Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have come across a sequence but I am facing difficulties finding the general term of it :

1 
1 1 
3 2 3 
5 3 3 5 
11 8 10 8 11 
21 13 14 14 13 21 
43 30 37 36 37 30 43 
85 55 61 55 55 61 55 85 
171 116 140 140 146 140 140 116 171 
341 225 256 232 226 226 232 256 225 341

Things which I have figured out :

  • Every row is palindromic

  • The first term of each row(>1) can be found out by 2*a[row-1][0]+ (-1)^(row-1)

  • 2nd term of each row(>2) is a[row][0] - a[row-1][1]

Please help me to find the general formula for such series

share|improve this question
    
For the first column: oeis.org/search?q=1%2C1%2C3%2C5%2C11%2C21&language=english. For the second column: oeis.org/…. –  Max Oct 3 '12 at 12:44
    
@Max : This is just the first and the last terms both of which I have mentioned in the post . –  Wayne Rooney Oct 3 '12 at 12:46
    
Look at the OEIS entries I've posted. They may be helpful, especially because the first suggests a different recurrence for the first column. –  Max Oct 3 '12 at 12:47
    
So, how did you come across this sequence? –  Gerry Myerson Oct 3 '12 at 13:04
    
@Gerry Myerson : I was solving a problem where two players(let them be A ,B ) are playing a game which consists of N coins in a row. Any player can pick up either the starting or the last coin in his turn. Player A begins . The above sequence is the number of times A picks up the jth coin when there are i coins initially in all possibilities. –  Wayne Rooney Oct 3 '12 at 13:16

3 Answers 3

up vote 2 down vote accepted

I think the following recursive scheme, reflecting the recursion of the pascal-triangle, shall be helpful. The parentheses contain the pascal-like summands north-east and north-west of an entry:

1                      =                    1-(0+0)
1 1                    =               2-(0+1)   2-(1+0)
3 2 3                  =           4-(0+1)   4-(1+1)   4-(1+0)
5 3 3 5                       8-(0+3)   8-(3+2)   8-(2+3)   8-(3+0)  
11 8 10 8 11           = 16-(0+5)  16-(5+3)  16-(3+3)  16-(3+5)  16-(5+0)
21 13 14 14 13 21      = ...

If the numbers of one row, index it with r beginning at 0, are taken as coefficents of a polynomial in x, call it $P_r(x)$ such that we have

$\qquad \begin{array} {} P_0(x)=1 \\ P_1(x)=1+1x \\ P_2(x)=3+2x+3x^2 \\ \ldots \end{array} $

then

$$ P_r(x) = 2^r \cdot {1-x^{r+1}\over 1-x} - (1+x)P_{r-1}(x) $$
[update:] error in index corrected

To expand the recursion into expressions based on the indexes only needs now only a bit more effort...


Here is the Pari/GP-routine, which produces the rows in terms of a polynomial in x using the recursion :

myPol(r)=if(r==0,return(1));2^r*(1-x^(r+1))/(1-x)  - (1+x)*myPol(r-1,x)  

The generated table of polcoeffs: $$ \small \begin{array} {rrrrrrrrrrr} 1 & . & . & . & . & . & . & . & . & . & . & . \\ 1 & 1 & . & . & . & . & . & . & . & . & . & . \\ 3 & 2 & 3 & . & . & . & . & . & . & . & . & . \\ 5 & 3 & 3 & 5 & . & . & . & . & . & . & . & . \\ 11 & 8 & 10 & 8 & 11 & . & . & . & . & . & . & . \\ 21 & 13 & 14 & 14 & 13 & 21 & . & . & . & . & . & . \\ 43 & 30 & 37 & 36 & 37 & 30 & 43 & . & . & . & . & . \\ 85 & 55 & 61 & 55 & 55 & 61 & 55 & 85 & . & . & . & . \\ 171 & 116 & 140 & 140 & 146 & 140 & 140 & 116 & 171 & . & . & . \\ 341 & 225 & 256 & 232 & 226 & 226 & 232 & 256 & 225 & 341 & . & . \\ 683 & 458 & 543 & 536 & 566 & 572 & 566 & 536 & 543 & 458 & 683 & . \\ 1365 & 907 & 1047 & 969 & 946 & 910 & 910 & 946 & 969 & 1047 & 907 & 1365 \end{array} $$

share|improve this answer

I tried deriving $ S _{n+2} $ from $ S _{n} $, and got something.
There are 4 ways to go $ S _{n+2} $ to $ S _{n} $ :
1) A selects first coin, B selects second coin $\space\space$:: [1,0] . $S_n$ (concat)
2) A select last one, B selects second last one :: $S_n$ . [0,1]
3) A selects first, first, B selects last $\space\space\space\space\space\space\space\space\space\space\space\space\space\space$ :: [1] . $S_n$ . [0]
4) A selects last, first, B selects first $\space\space\space\space\space\space\space\space\space\space\space\space\space\space$ :: [0] . $S_n$ . [1]

for eg, operating on [5 3 3 5] gives:
[1 0 5 3 3 5] + [5 3 3 5 0 1] + [1 5 3 3 5 0] + [0 5 3 3 5 1]
$\equiv$ [7 13 14 14 13 7]

Tried on othe examples, all numbers except the last and the first ones are coming correct (can somebody point out why?) Otherwise the first terms can be calculated by the formula $\frac{2^n - (-1)^n}{3}$

share|improve this answer
    
That's good! The trouble is that wherever you have 1, you should have the number of different ways the length $n$ game can go. E.g., there are 8 ways that $n=4$ can go (abab, abba, aabb, abab when 1st player starts on the left, 4 more where 1st player starts on the right), so you want 8 0 5 3 3 5 + 5 3 3 5 0 8 + 8 5 3 3 5 0 + 0 5 3 3 5 8 = 21 13 14 14 13 21. –  Gerry Myerson Oct 4 '12 at 8:45
    
Oh yes! You add your answer, mine is anyways more of a comment =) –  piyush Oct 4 '12 at 8:51
    
Done.${}{}{}{}$ –  Gerry Myerson Oct 4 '12 at 12:53

Let $f(n,k)$ be the number of times A picks up the $k$th coin when the game starts with $n$ coins. Note that the total number of ways an $n$ coin game can go is $2^{n-1}$, since each player has 2 options at each move, except the last move, which is forced. Then by the reasoning in the answer by piyush and my comment, we have the following equations. $$\eqalign{f(n+2,1)&=2^n+f(n,1)\cr f(n+2,2)&=2f(n,1)+f(n,2)\cr f(n+2,k)&=f(n,k)+2f(n,k-1)+f(n,k-2)\cr}$$ The third equation holds for $3\le k\le n-2$. Also, $f(n+2,n+1)=f(n+2,2)$, and $f(n+2,n+2)=f(n+2,1)$.

This gives a formula for the numbers in the table, but of course it's a recursive formula. Whether this system of equations can be solved in closed form, I don't know.

EDIT: For any fixed $k$ it shouldn't be too hard to get a formula for $f(n,k)$ as a function of $n$. Let's just take the case $n$ odd. From $$f(n+2,1)=2^n+f(n,1)$$ we get $$f(n,1)=2^{n-2}+2^{n-4}+\cdots+2^1+f(1,1)$$ and summing the geometric series we get $$f(n,1)={2^n+1\over3}$$ Then from $$f(n+2,2)=2f(n,1)+f(n,2)$$ we get $$f(n,2)=(2/3)(2^{n-2}+1+2^{n-4}+1+\cdots+2^1+1)$$ and there's another geometric series to sum. Now you can play the same game with $$f(n+2,3)=f(n,3)+2f(n,2)+f(n,1)$$ and so on. Perhaps a pattern emerges if you do enough of these.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.