1
$\begingroup$

How to find number of presentations of 1 as a sum of exactly $k$ numbers of the form $2^{-i}$ ? As an example for $k=2$ we have only one presentation: $$1 = \frac{1}{2} + \frac{1}{2},$$ so answer for $k = 2$ is 1. For $k=4$, $$1 = \frac{1}{2} + \frac{1}{4} + \frac{1}{8} + \frac{1}{8}$$ and $$1 = \frac{1}{4} + \frac{1}{4} + \frac{1}{4} + \frac{1}{4},$$ so the answer is 2.

How to find the formula for all $k$?

$\endgroup$
14
  • 1
    $\begingroup$ So you me sum of powers of $2^{-1}?$ $\endgroup$
    – Thomas Andrews
    Mar 26 at 14:29
  • 1
    $\begingroup$ Generating function, but it doesn't seem to get us anywhere. Consider: $$f_m(w,z)=\prod_{j=0}^{m}\frac1{1-wz^{2^{j}}}$$ Then you want to find the coefficient of $w^kz^{2^m}$ for $m=\lfloor \log_2 k\rfloor.$ But I don't immediately see how to do that. $\endgroup$
    – Thomas Andrews
    Mar 26 at 14:39
  • 2
    $\begingroup$ But ... @rrryok ... How is $1=\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+\frac{1}{8}$ a sum of $2^{-1}$'s? $\endgroup$
    – user700480
    Mar 26 at 14:48
  • 3
    $\begingroup$ This is oeis.org/A002572 $\endgroup$
    – JBL
    Mar 26 at 15:12
  • 1
    $\begingroup$ This came up again today: Find a formula for this sequence: 1,1,1,2,3,5,9,16,28,50,89... $\endgroup$
    – MJD
    Mar 26 at 20:43

0

Reset to default

Browse other questions tagged .