3

I'm trying to prove the well-known identity $$\sum_k {n \choose k} = 2^n$$ with exponential generating functions (egf's). The idea is to note that the egf of the left hand side and the right hand side are the same. (Note that I don't actually care about proving this identity. It's the conceptual issue below that I care about.)

Here is my proof:

The left hand side is the binomial transform of the constant sequence $a_n = 1$, so its egf is $e^x e^x$. The right hand side has egf $$\sum_{k \geq 0} \frac{2^k}{k!} x^k = e^{2x}.$$ Since $e^x e^x = e^{2x}$, we're done.

But this confuses me. When I write $e^x e^x$ on the left hand side, I understand that to mean the product of two generating functions. When I write $e^{2x}$ on the right hand side, I understand it to mean the egf of the sequence $a_n = 2^n$. As analytic functions I know that these two are equal, but as generating functions I do not. That's exactly what I want to prove.

Can this proof be made valid? Specifically, can it be made valid without referencing analytic properties or the binomial theorem?

Robert D-B
  • 2,206
  • 1
    The idea of the cited proof is to borrow analytic properties into the argument, which is possible because convergent power series can be identified as a generating function (formal power series). If such borrowing is prohibited, then $e^x$ is more or less a fancy naming for the generating function $\sum_{n=0}^{\infty} x^n/n!$ whose properties are to be studied. – Sangchul Lee Apr 27 '19 at 15:42
  • 2
    You can use the fact that $e^{ax}$ is the unique power series solution of the differential equation $f'=af$ with initial condition $f(0)=1$. Before complaining about still having to do analysis, note that here the differentiation can be taken to be formal differentiation of formal power series. – Angina Seng Apr 27 '19 at 16:33

1 Answers1

3

If you like, we're using a little theorem from complex analysis, that the only convergent power series for the zero function is $0$. It follows that if two convergent power series are equal as functions in a neighborhood of the origin, then their coefficients are termwise equal.

hunter
  • 29,847
  • (In other words, you're right to worry that there's a distinction between formal power series and functions, but in fact one checks as a theorem that they are not distinct -- provided we have convergence so that the function approach makes sense at all -- so you can argue in either world.) – hunter Apr 27 '19 at 15:39
  • Does this "analytic-formal correspondence" theorem have a name? I hear it mentioned all the time but haven't ever seen it stated or proven. That might answer some of my questions as to when this technique is valid. – Robert D-B Apr 27 '19 at 23:34
  • @rwbogl sometimes this is called the "identity theorem" (that holomorphic functions are determined by their restrictions to any open -- actually any set with an accumulation point) – hunter Apr 28 '19 at 00:21