Check out the book $A=B$ by Zeilberger, Wilf, and Petkovsek.

It’s all about how to prove essentially any combinatorial identity like this that you can think of.

The moral of the story is you type it into your computer, hit enter, and let it verify it for you and produce a certificate. These algorithms are all definitely available as packages for Maple and Sage. It might even be part of the standard Maple library.

**Added:**

*"Science is what we understand well enough to explain to a computer. Art is everything else we do. During the past several years an important part of mathematics has been transformed from an Art to a Science: No longer do we need to get a brilliant insight in order to evaluate sums of binomial coefficients, and many similar formulas that arise frequently in practice; we can now follow a mechanical procedure and discover the answers quite systematically. I fell in love with these procedures as soon as I learned them, because they worked for me immediately. Not only did they dispose of sums that I had wrestled with long and hard in the past, they also knocked off two new problems that I was working on at the time I first tried them. The success rate was astonishing. ..."* -- Donald Knuth (taken from the Foreward of $A=B$)

The full text for $A=B$ is available here free of charge, and the authors wanted to make sure anyone who wanted it could have it without paying.

(It really is magic, by the way. Give it a try!)