2
$\begingroup$

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

  • 0
    Have a look at http://math.stackexchange.com/questions/208126/probability-of-picking-kth-item-at-odd-turn which is essentially the same problem.2012-10-07

3 Answers 3

2

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} $

1

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}$

  • 0
    Done.${}{}{}{}$2012-10-04
1

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.