f ( x ) = k = 0 ∏ ∞ ⎝ ⎛ n = 0 ∑ A − 1 x n A k ⎠ ⎞
Find the value of f ( 2 1 ) , given that A is an integer greater than 1.
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.
Nice! This is exactly what inspired this problem!
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 }
Similar solution with @Aditya Dhawan 's presented as follows.
f ( x ) = k = 0 ∏ ∞ n = 0 ∑ A − 1 x n A k = k = 0 ∏ ∞ 1 − x A k 1 − x A k + 1 = ∏ k = 0 ∞ ( 1 − x A k ) ∏ k = 1 ∞ ( 1 − x A k ) = 1 − x A 0 1 = 1 − x 1 Sum of a GP for ∣ x ∣ < 1
⟹ f ( 2 1 ) = 1 − 2 1 1 = 2 .
Problem Loading...
Note Loading...
Set Loading...
Interpret f ( x ) as a generating function. The coefficient of x p counts the number of ways to partition p such that each part is in the form A k for some non-negative integer k , and no part appears more than A − 1 times. (To see this, observe that ∑ x n A k gives n parts, all equal to A k .)
For any integer p , there is exactly one such partition: interpret p in base A . For example, for p = 7 , A = 3 , we have p = 2 1 3 , or p = 2 ⋅ 3 1 + 1 ⋅ 3 0 . Thus the required partition is 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 . Consider the largest difference; that is, the largest A k that appears in one partition and not in the other. The sum of all smaller parts cannot be equal to A k ; it's at most ( A − 1 ) ( A k − 1 + A k − 2 + … + A 0 ) = A k − 1 . Thus the partition with 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 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 , we can rewrite f ( x ) in a more standard generating function form: ∑ p = 0 ∞ x p , because the coefficient of x p counts the number of such partitions of p , which is 1 for all p . Thus f ( x ) = ∑ p = 0 ∞ x p = 1 − x 1 with radius of convergence 1. Since ∣ ∣ 2 1 ∣ ∣ < 1 , f ( 2 1 ) converges, and we can compute its value with that formula: 1 − 2 1 1 = 2 .