Background

Essentially, I was playing around with some interpolation-related ideas using various sequences to try and derive existing identities. What I came across eventually was the alternating sum of binomial coefficients, which I've somehow derived to be equal to $0$. What I didn't realise was is that I had made a bad assumption, but had, in fact, arrived at the correct result (assuming that this sum was in fact zero).

After I attempted a similar thing as above with prime numbers and getting a nonzero sum, I got thinking, and applied the same methods to a general sequence with only distinct elements, let's say $\{a_n\}$, and arrived at the following two sums: $$ A_n=\sum_{k=1}^{n}{\prod_{\substack{j=1\\j\neq k}}^{n}{\frac{1}{a_j-a_k}}} $$

$$ B_n=\sum_{k=1}^{n}{\prod_{\substack{j=1\\j\neq k}}^{n}{\frac{a_j}{a_j-a_k}}} $$

With the help of Mathematica, I conjectured that for $n\geq 2$, $A_n=0$ and that for $n\geq 1$, $B_n=1$ (since the empty product gives $1$).

Given the nature in which these sums simplify; that is, when combined into a single fraction so to speak, I'm fairly confident these patterns continue for all respective $n$... whatever those patterns might be.

Attempts

One of the most natural things to do in this context was to recognise these sums as being resultant of lagrange interpolation. Unfortunately, all my attempts to do this for both problems resulted in a situation where multiple values of $x$ were needed for the numerator of each fraction to be satisfied as in these sums. It may be possible that there exists a trick, such as multiplying and dividing by something specific, for which this method may be viable, but I haven't found it yet.

Another fairly obvious approach was to attempt induction on these problems. Only, instead, we run into a different problem - how does one even begin to factor $A_{n+1}$ in terms of $A_n$ with extra terms? One might consider separating the $k=n+1$ case for both sum and product; but then we're left with a coefficient we can't get rid of in the summands. An identically difficult method was to try and show that $A_{n+1}-A_{n}=0$, but no such luck again, especially with factoring.

Knowing induction, there's often a trick for which one might go about simplifying the problem, but I have again yet to find such a trick.

In the spirit of doing things by hand, I also attempted to make a common denominator with each of the terms. The problem with this approach is that generally speaking, I don't know of any ways to (in general) expand each factor, and secondly, the expressions ended up nesting yet another product inside. That is, given that the numerator $=0$ implies the expression overall is $0$ (since the denominator is nonzero). For $A_n$, it looked something like this: $$ \sum_{k=1}^{n}{\prod_{\substack{j=1\\j\neq k}}^{n}{\prod_{\substack{m=1\\m\neq j}}^{n}{(a_m-a_j)}}} $$ I also returned to how I had derived such sums. No such luck there, unfortunately.

Summary

How would one go about proving or disproving the following identities: $$ \sum_{k=1}^{n}{\prod_{\substack{j=1\\j\neq k}}^{n}{\frac{1}{a_j-a_k}}}=0,\quad n\geq 2 $$

$$ \sum_{k=1}^{n}{\prod_{\substack{j=1\\j\neq k}}^{n}{\frac{a_j}{a_j-a_k}}}=1,\quad n\geq 1 $$

Or, where might one begin with these problems, seeing as we're dealing with a nested sum and product? Much more importantly, what might be some other techniques worth considering to show, or disprove the above?

(On a sidenote, if relevant, what exactly makes these problems so seemingly difficult?)

Welcome to MSE!

First, your idea regarding lagrange interpolation is a great one! The key insight is to look at particular coefficients in order to make your life easier.

So, let's let $a_1, \ldots a_n$ be some complex numbers. Then let's find a polynomial interpolating the points $(a_1, 1), (a_2, 1), \ldots, (a_n, 1)$.

On the one hand, we know that this is the constant $1$ polynomial. On the other, we know it's some horrible linear combination:

$$ 1 = \sum_{k=1}^n \prod_{j \neq k} \frac{x - a_j}{a_k - a_j} $$

But now let's compare the $x^{n-1}$ coefficient of both sides! On the left hand side, we get $0$. On the right hand side, we get $\sum_{k=1}^n \prod_{j \neq k} \frac{1}{a_k - a_j}$.

Similarly, let's compare the $x^0$ coefficients! On the left hand side we get $1$, and on the right hand side we get $\sum_{k=1}^n \prod_{j \neq k} \frac{-a_j}{a_k - a_j} = \sum_{k=1}^n \prod_{j \neq k} \frac{a_j}{a_j - a_k}$.

To see why these are both true, let's separate the numerators and denominators of our polynomial:

$$ 1 = \sum_{k=1}^n \left ( \prod_{j \neq k} \left ( \frac{1}{a_k - a_j} \right ) \prod_{j \neq k} \left ( x - a_j \right ) \right ) $$

Now, if we want the $x^{n-1}$ term, we need to get the $x^{n-1}$ term of each product. But imagine foiling out $\prod_{j \neq k} (x - a_j)$. The coefficient of $x^{n-1}$ is $1$. If we do this for each summand, we find

$$ 0 x^{n-1} = \sum_{k=1}^n \prod_{j \neq k} \left ( \frac{1}{a_k - a_j} \right ) x^{n-1} $$

which gives the claim.

Similarly, if we want the constant term, we need to get the constant term of each product. Again, if we imagine foiling out the $\prod_{j \neq k} (x - a_j)$, we find the constant term is exactly $\prod_{j \neq k} (-a_j)$. Doing this to each term of the sum shows

$$ 1 = \sum_{k=1}^n \left ( \prod_{j \neq k} \left ( \frac{1}{a_k - a_j} \right ) \prod_{j \neq k} (- a_j) \right ) $$

now if we recombine these products (and juggle some minus signs), we get the desired

$$ 1 = \sum_{k=1}^n \prod_{j \neq k} \frac{a_j}{a_j - a_k}. $$

Now, let's address some of your closing questions.

• Where might one begin with these problems?

Exactly where you began! Working out lots of concrete examples, conjecturing something to be true, and then trying to prove it! Your idea to look at lagrange interpolation was an excellent one, and it was only the idea to look at the polynomials one coefficient at a time that you were lacking. I'm sure if you spent another day or two with this problem you would have gotten it.

As a slightly more productive answer, you need to know what's the right level of generality to use when working out "concrete" examples. For instance, it's probably best in this problem to keep the $a_i$ as symbolic constants, rather than considering the special case of, say $a_1 = a_2 = a_3 = 2$. That said, it is fruitful to work with the special cases $n = 1, 2, 3, \ldots, 5$, say. These can all be worked out without too much hassle (especially if you use a computer algebra system, as you mention you did), and can give you some useful information.

In particular, the notion of a normal form is extremely useful, and whenever you're working with two objects that you know are equal, you should try and put them into some kind of normal form and compare the pieces separately. For this problem, that means expanding the lagrange polynomial into its normal form $c_0 + c_1 x + c_2 x^2 + \ldots + c_{n-1} x^{n-1}$. If you had done this for some small examples, you would have doubtless seen the pattern in the coefficients that later became the proof.

• What makes these hard?

In an informal way, problems that involve both addition and multiplication simultaneously are "hard". This "prototheorem" can be made precise in a number of ways (see skolem and presburger arithmetic compared with robinson arithmetic, for instance), but informally it permeates lots of questions. There are lots of open problems whose difficulty lies, in some sense, in trying to see how addition and multiplication interact. This means that problems that blend addition and multiplication are necessarily trickier than problems which only feature one of the two. I'm sure that this is also accurate to your lived experience.

Of course, I'm sure there are some tricks for dealing with these things, but I'm far from an expert, so I don't know any off the top of my head. I tend to tackle these on a fairly ad-hoc basis, and would also love to hear about a more systematic approach!

I hope this helps ^_^