Comment by GistNoesis

Is the recursion relation you use https://en.wikipedia.org/wiki/Hockey-stick_identity ? Are you sure you can't use https://en.wikipedia.org/wiki/Pascal%27s_rule instead for a simpler recursion. Have you also tried using https://en.wikipedia.org/wiki/Vandermonde%27s_identity ?