Thank you to Stacey from Wales High School, Dmitri from Cork in Ireland, and many others for ideas about what's going on here.

If you start with 8 cards you end up with the number 8, and if you start with 9 cards you end up with the number 2.

If you start with 2 or 4 or 8 or 16 the last card is 2, 4, 8 or 16 to match.

After any one of those, for example 9 after 8, the last card moves on by 2.

So 8 cards finishes with 8, 9 cards finishes with 2, 10 cards finishes with 4, 11 cards finishes with 6, and so on until 14 finishes with 12, 15 finishes with 14 and 16 (the next power of 2 after 8) finishes with 16.

Then it all happens again, in the same way : 17 cards finishes with 2, 18 cards with 4 and so on.

Here's why that happens

For example starting with : 1 2 3 4 5 6 7 8
Every second card is kept and we get : 2 4 6 8
Half the cards have gone, the second card of each pair.
The same thing happens and we are left with: 4 8
Half the cards have been lost again, as before the second card in each pair has gone.
Finally 4 8 goes down to 8

It's always the second card of the pair that stays in.
So when the number of cards is a plain power of 2, like 8, only half the cards stay, then only half of those, and so on until it's just the end card, like 8, that remains.

Now for the other numbers :

Start at a plain power of two, like 8, and increase by 1, that's 9, and make the first move of 'one out and one under'.
Now we have 8 cards again, we had 9 but one's gone out.
And for 8 we know what will happen, we'll be left with the last card in that order as the final card remaining.
So what's the order ?
We've done one out and one under so all positions will have moved by two cards.
So we don't finish on the 8, or the next card (1 - it's out), but the one after that, that's the 2.

Make the first move : 'one out and one under'.
And then there are 9 cards and we know that that will finish with 2, but all the positions have moved by 2 places, so the final card is the 4.

The same thing happens again and again - when there's one more card at the start the last card moves 2 on from the previous result.

Nice reasoning !

Here is a table sent in to us by  children at Weston Turville CE School:

 Start Card 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Card Left 2 2 4 2 4 6 8 2 4 6 8 10 12 14 16

 Start Card 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 Card Left 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32

In the table shown you can see that every time that you have a number of cards to start with that is a power of $2$ i.e. $\{2, 2^2, 2^3, 2^4, 2^5, 2^6\}$ then it results in itself.