Product of sums

Calculus Level 3

f ( x ) = k = 0 ( n = 0 A 1 x n A k ) \displaystyle \large f(x) = \prod _{k=0}^{\infty}\left(\sum _{n=0}^{A-1}x^{nA^k}\right)

Find the value of f ( 1 2 ) f \left(\frac 12 \right) , given that A A is an integer greater than 1.


The answer is 2.00.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

3 solutions

Ivan Koswara
Dec 11, 2016

Interpret f ( x ) f(x) as a generating function. The coefficient of x p x^p counts the number of ways to partition p p such that each part is in the form A k A^k for some non-negative integer k k , and no part appears more than A 1 A-1 times. (To see this, observe that x n A k \sum x^{nA^k} gives n n parts, all equal to A k A^k .)

For any integer p p , there is exactly one such partition: interpret p p in base A A . For example, for p = 7 , A = 3 p = 7, A = 3 , we have p = 2 1 3 p = 21_3 , or p = 2 3 1 + 1 3 0 p = 2 \cdot 3^1 + 1 \cdot 3^0 . Thus the required partition is 3 1 + 3 1 + 3 0 3^1 + 3^1 + 3^0 . It's easy to see that there is no other such partition. Suppose there is one such partition besides the one obtained through base A A . Consider the largest difference; that is, the largest A k A^k that appears in one partition and not in the other. The sum of all smaller parts cannot be equal to A k A^k ; it's at most ( A 1 ) ( A k 1 + A k 2 + + A 0 ) = A k 1 (A-1)(A^{k-1} + A^{k-2} + \ldots + A^0) = A^k - 1 . Thus the partition with A k A^k must have larger sum; in particular, they don't sum to the same number, thus one of them is invalid. Since the base A A one is a valid partition, our assumed partition must be the invalid one.

Now that we know there is one such partition for each p p , we can rewrite f ( x ) f(x) in a more standard generating function form: p = 0 x p \sum_{p=0}^\infty x^p , because the coefficient of x p x^p counts the number of such partitions of p p , which is 1 for all p p . Thus f ( x ) = p = 0 x p = 1 1 x f(x) = \sum_{p=0}^\infty x^p = \frac{1}{1-x} with radius of convergence 1. Since 1 2 < 1 \left| \frac{1}{2} \right| < 1 , f ( 1 2 ) f \left( \frac{1}{2} \right) converges, and we can compute its value with that formula: 1 1 1 2 = 2 \frac{1}{1 - \frac{1}{2}} = \boxed{2} .

Nice! This is exactly what inspired this problem!

Julian Poon - 4 years, 6 months ago
Aditya Dhawan
Dec 8, 2016

f\left( x \right) =\lim _{ n\longrightarrow \infty }{ \prod _{ k=0 }^{ n }{ \left( \sum _{ n=0 }^{ A-1 }{ { x }^{ n{ A }^{ k } } } \right) } =\quad } \\ \lim _{ n\longrightarrow \infty }{ \prod _{ k=0 }^{ n }{ \frac { { x }^{ { A }^{ k+1 } }-1 }{ { x }^{ { A }^{ k } }-1 } } } =\quad \lim _{ n\longrightarrow \infty }{ \frac { { x }^{ { A }^{ n+1 } }-1 }{ { x }-1 } } =\boxed { \frac { 1 }{ 1-x } } \quad \quad \quad \left\{ \left| x \right| <1 \right \\ \\ \therefore \quad f\left( \frac { 1 }{ 2 } \right) =\quad \boxed { 2 }

Chew-Seong Cheong
Dec 13, 2016

Similar solution with @Aditya Dhawan 's presented as follows.

f ( x ) = k = 0 n = 0 A 1 x n A k Sum of a GP = k = 0 1 x A k + 1 1 x A k for x < 1 = k = 1 ( 1 x A k ) k = 0 ( 1 x A k ) = 1 1 x A 0 = 1 1 x \begin{aligned} f(x) & = \prod_{k=0}^\infty \color{#3D99F6} \sum_{n=0}^{A-1} x^{nA^k} & \small \color{#3D99F6} \text{Sum of a GP} \\ & = \prod_{k=0}^\infty \color{#3D99F6} \frac {1-x^{A^{k+1}}}{1-x^{A^k}} & \small \color{#3D99F6} \text{for } |x| < 1 \\ & = \frac {\prod_{k={\color{#D61F06}1}} ^\infty (1-x^{A^k})}{\prod_{k={\color{#D61F06}0}}^\infty (1-x^{A^k})} \\ & = \frac 1{1-x^{A^{\color{#D61F06}0}}} \\ & = \frac 1{1-x} \end{aligned}

f ( 1 2 ) = 1 1 1 2 = 2 \implies f \left(\frac 12\right) = \dfrac 1{1-\frac 12} = \boxed{2} .

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...