I also got 2^(n-1).

Here is a print out of the solutions for n=3 and n=4

    (1, 2, 3)

    (1, 3, 2)

    (3, 1, 2)

    (3, 2, 1)  when n=3, answer = 4 = 2^(n-1)

    (1, 2, 3, 4)

    (1, 2, 4, 3)

    (1, 4, 2, 3)

    (1, 4, 3, 2)

    (4, 1, 2, 3)

    (4, 1, 3, 2)

    (4, 3, 1, 2)

    (4, 3, 2, 1)

Work out the n=4 solution given that we already know it for n=3.

4 can be the first number.  Since 4 is now "out of the way", the remaining 3 slots can be filled exactly like they were for n=3.

1 can be the first number.  Same argument except for each n=3 solution, just add 1 to each number and the entire n=3 solution is recapitulated.

So far, we have exactly twice the number of solutions by increasing n from 3 to 4.

Can a valid permutation begin with 2 or 3, or more generally, any number other than 1 or n?

No.

Consider that each number has two "buddies" the one above and the one below; except for 1 and n who have just one buddy each.  Suppose 2 is in position 1. Where will you place the 1?  1 has no buddies remaining to be to his right, so 1 has to go in the final position; but that won't work because now no one qualifies for the second to last position.  A similar argument can be made for why 3 cannot be in position number 1 (where would you put the 4?)

This pigeonhole argument can no doubt be extended to larger numbers, which I haven't done, but this is close to a proof.