General term of a double dimensional sequence 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
 A: 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}$
A: 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. 
