1. Yes, Prof. Argyle is correct.  If the encoding of X was strictly
shorter than that for Y, i.e., the depth of X in the tree was strictly
less than that of Y, then swapping X and Y in the tree would strictly
improve the effectiveness of the encoding scheme.  Since the Huffman
coding algorithm finds the optimal tree, this is impossible.


2. You can do it in O(n) time by computing F-values in the order
F(n,0), F(n,1), F(n-1,0), F(n-1,1), F(n-2,0), F(n-2,1), etc.: i.e.,
by decreasing value of x.

Alternatively: you can do it in O(n) time if you think of the
problem as defining a recursive function F(.,.) and you apply
memoization.


Comment: If you think of problem as defining a recursive function
F(.,.) and you just call F(1,1), you'll get a solution that is very
inefficient: it will take O(2^n) time.  For instance, F(1,1) will
evaluate F(2,0) and F(2,1).  The call to F(2,0) will invoke F(3,0),
and the call to F(2,1) will invoke F(3,0) a second time.  So naively
executing this recursive function will cause many repeated recursive
calls with the same inputs, a total waste of time.  Memoization is
one way to address this.