I have the exact same problem, but my reputation is not enough to comment on that thread, plus the OP hasn't been online in 2 years so I can't ask him personally. So I apologize, but I do have to ask for your help!
Would it be enough to show that the formula works for n = 2, n = 3 (by drawing the automata) and deduct that it must work for any n?
As for the second question, could I follow the same strategy?
Thank you for you time.