2
$\begingroup$

Recently, I’ve learned about generating functions. From my understanding you basically represent each “option” with a polynomial, and the resulting polynomials multiplied would give coefficients related to the number of ways you can choose some objects.

So here, I’m trying to apply the same thing to binary numbers! Using $x^{2^n}+1$ to represent 2^n in binary and multiplying first 3 terms of it i.e. $(x+1)(x^2+1)(x^4+1)=\sum_{i=0}^7x^i$ I can show that 0-7 has unique representation in binary! 🤗

However, I would like to prove this for all natural numbers. Simple, simply multiply $\Pi_{i=0}^\infty (x^{2^i}+1) $😋 what I would get would be $1+x+x^2+...$. Ayyy! $\frac{1}{1-x}$! I quickly write down

Some might see the problem here, but we said that $\frac{1}{1-x}=\Pi_{i=0}^\infty x^{2^i}+1$. The problem here is that (I GIVE UP PHONE LATEX) LHS has no roots while RHS has infinitely many roots i.e. x=1, x^2=-1, ...

$$\frac{1}{1-x}=\Pi_{i=0}^\infty x^{2^i}+1 $$

question: why do they not match in terms of roots, even though they “clearly is the same”?

Also I believe you can do the same “factorisation” in different “base”. Is the factorisation even valid? It’s not unique though...

Gareth 😛😥

Sorry it’s hard to type and format latex on phone

$\endgroup$
  • 1
    $\begingroup$ You are on to something subtle and interesting and useful. You might enjoy scrolling down here to read Euler's argument for the sum of the reciprocals of the squares. plus.maths.org/content/infinite-series-surprises $\endgroup$ – Ethan Bolker Mar 24 at 13:31
  • 1
    $\begingroup$ Factorising $sin(x)$... Wow! Also I found this thing which i do not understand: Weierstrass factorization theorem $\endgroup$ – Gareth Ma Mar 25 at 3:35
3
$\begingroup$

They are not the same. $\frac{1}{1 - x} = \sum_{i = 0}^\infty x^i$ only when $|x| < 1$. All the roots of the infinite polynomial occur when this condition is not satisfied. In fact, $|r| = 1$ for all roots $r$.

You can do this factorization in any base if you include as the exponents all multiples of the powers of the base up to $b - 1$. So for base three, the product would be $\prod_{i = 0}^\infty (1 + x^{3^i}+x^{2 \cdot 3^i})$

$\endgroup$
2
$\begingroup$

We want to show that $$\frac{1}{1-x} = (1+x)(1+x^2)(1+x^4)(1+x^8)\cdots $$ An equivalent statement is $$1 = (1-x)(1+x)(1+x^2)(1+x^4)(1+x^8)\cdots \tag{*}$$ Now notice that $$\begin{align} (1-x)(1+x)(1+x^2)(1+x^4)(1+x^8)\cdots &= (1-x^2)(1+x^2)(1+x^4)(1+x^8)\cdots \\ &= (1-x^4)(1+x^4)(1+x^8)\cdots \\ &= (1-x^8)(1+x^8) \cdots \\ & \vdots \end{align}$$ from which we conclude that the infinite product is equal to $1$, proving $(*)$.

In working with generating functions, we often do not worry about questions of convergence of series; rather, we regard the series as formal objects subject to certain rules. This is OK so long as we do not attempt to actually evaluate the series, but if we do evaluate the series then questions of convergence apply. So it would be incorrect to attempt to evaluate the infinite product $(*)$ at $x=i$, for example, because the product does not converge there.

$\endgroup$
  • $\begingroup$ Oh! So the problem is that when I'm "finding the root" of both sides, it actually doesn't converge on the "roots"? But otherwise, in the convergence radius, everything's "fine"? Thanks $\endgroup$ – Gareth Ma Mar 25 at 3:21
  • $\begingroup$ @GarethMa That's right, the series for $1/(1-z)$ converges for $|z| < 1$, so don't expect reasonable results for $|z| \ge 1$. $\endgroup$ – awkward Mar 25 at 12:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.