Faster, More Elegant Way to Produce a Recursive Sequence of Rational Numbers

ClearAll[B];    
B[k_]:=B[k]=Simplify[FunctionExpand[-1/(Binomial[n+k,k])*Sum[Binomial[n+k,j]*B[j],{j,0,k-1}]]]

Works fine for me:

Table[{"B[" <> ToString[k] <> "]=", B[k]}, {k, 0, 7}] // TableForm

Make sure to ClearAll[B] when changing the definition since the values are cached by B[k]:=B[k]. Computing B[k] up to k=7 took 0.02 seconds for me and up to k=42 it took 10.7 seconds. That seems reasonable to me.

Just pointing out the difference between OP's definition and N0va's:

Incorrect version

B[k] = B[k_] := <RHS>

Reading from left to right, the first assignment is single-equals (Set) while the second assignment is colon-equals (SetDelayed). Notice that in the GUI, k appears blue (assuming it is free). In pseudocode:

1. Mathematica first sees B[k] = <expression1>, and says, "I will immediately evaluate <expression1> and assign the result to B[k]."
2. Mathematica then sees <expression1>, which is B[k_] := <RHS>, and says, "I will now define B[k_] to be <RHS>, but I will delay the evaluation of <RHS> until I receive an actual value of k."

The second step returns Null, and it is this Null that gets immediately assigned to B[k]. Effectively this is the same as doing

B[k_] := <RHS>
B[k] = Null

i.e. an unmemorised definition followed by an immediate (but rather useless) assignment.

Correct version

B[k_] := B[k] = <RHS>

Reading from left to right, the first assignment is colon-equals (SetDelayed) while the second assignment is single-equals (Set). In pseudocode:

1. Mathematica first sees B[k_] := <expression2>, and says, "I will now define B[k_] to be <expression2>, but I will delay the evaluation of <expression2> until I receive an actual value of k."

OK, so what happens when an actual value of k is received?

2. Mathematica then evaluates <expression2>, which is B[k] = <RHS>, and says, "I will now immediately evaluate <RHS> and assign the result to B[k]." It is this second assignment which achieves the memorisation.