IBM Ponder This #086 · June 2005

Puzzle for June:

This puzzle is based on a suggestion by Aditya K Prasad,
(Further attribution will be given with the solution.)

Consider a string S of N symbols, selected from the set {A,B}.
In any consecutive substring of S,
the number of A's differs from the number of B's by at most 3.
How many such strings S are there (as a function of N, in closed form)?

---

We are not accepting solutions for this month.

Solution

Best opened after a real attempt

To be added.