Proof (by induction): We will show that Bill can win if Ann starts with
a heap of Fn (for certain n) mats.
The number n has to be at least 3, because for n=1 or n=2
there is only a "heap" of 1 biermat.
Ann is not allowed to take all biermats in her first turn,
thus the requirements are contradictory for 1 biermat.
We will proof the following statement:
Bill can win if Ann starts with a heap of Fn (for certain n) mats.
Bill takes in his winning (= last) turn Fn-1 mats or less.
The hypothesis is true for n=3 and for n=4, because:
For n=3 there are 2 mats.
From this pile Anneke has to take 1 and after that Bill takes 1
(=Fn-1) and wins.
For n=4 there are 3 mats. Ann may take 1 mat from the heap. Then Bill takes 2(=Fn-1) mats, or Ann takes 2 mats and Bill 1(<Fn-1) mat.
In both cases Bill wins.
In short, the hypothesis is correct for n=3 and for n=4.
Suppose that we have allready shown that the hypothesis is correct for all n<N.
Then we will show that the hypothesis is also correct for n=N.
We know that FN = FN-1 + FN-2.
We divide (in memory) the stack in two parts.
On the lower part of FN-1 mats there lie
FN-2 mats.
Remember that Bill can allways win when the heap consists of FN-2 biermats (according to the hypothesis).
So he can see to it that after a number of moves there are
(the last move with less than FN-3 mats) still FN-1 mats left
(unless Ann takes FN-2 or more mats in her first move, but in that case Bill wins by taking all the mats that are left;
Then Bill's winning move consists of less than FN-1 mats.).
Bill will win, independent of Ann's next move, for Bill can allways win
when there are FN-1 mats (according to the hypothesis),
and Ann is not allowed to take all mats, for 2*FN-3 < FN-1.