recurrence generating functionstirling number recreational problem

[floral compass]

I woukd try the reduce and conquer tactic

Fix k=1, for any n>0 there is exactly one string that does not contain w, can you prove this?

If you can, then you can fix k=2, prove that for any n>1 there is exactly m string that does not contain w

m is a variable which is 1 for k=1, and has other values for other k's

Most recreational mathematics problems can be solved by reduce and conquer, no matter how many variables there are, always try a few simplest cases, good luck

Do you have the value of m for k=2?

[minor kelp]

it can't be the same answer for any string

look

0 0 0 -
0 0 1
0 1 0 +
0 1 1 +
1 0 0 -
1 0 1 +
1 1 0 + -
1 1 1 + -

• is when w = 00
  - is when w = 01

there's more + than -

[minor kelp]

.close