Σειρά pop

Tolaso J Kos · #1

Ας μετράει το ${\rm pop}$ τον αριθμό των bits του '1' στη δυική αναπαράσταση του

. Υπολογίσατε τη σειρά

$\displaystyle{\mathcal{S} = \sum_{n=1}^{\infty} \frac{{\rm pop}(n)}{n(n+1)}}$

dement · #2

Καλό. Μετακινούμαστε από δεξιά προς αριστερά στο δυαδικό.

Οι περιττοί αριθμοί έχουν το ψηφίο των μονάδων

. Το αντίστοιχο μερικό άθροισμα είναι $\displaystyle \frac{1}{1\cdot 2} + \frac{1}{3 \cdot 4} + ... = \ln 2$ .

Οι αριθμοί με υπόλοιπο

ή

ως προς

έχουν το ψηφίο των δυάδων

. Το αντίστοιχο μερικό άθροισμα είναι $\displaystyle \frac{1}{2 \cdot 3} + \frac{1}{3 \cdot 4} + ... = \frac{1}{2} - \frac{1}{4} + \frac{1}{6} - ... = \frac{1}{2} \ln 2$

Ομοίως για το ψηφίο των τετράδων $\displaystyle \frac{1}{4} \ln 2$ και ούτω καθεξής.

Τελικά το άθροισμα είναι $\displaystyle \ln2 \sum_{k=0}^{\infty} \frac{1}{2^k} = 2 \ln 2$

Tolaso J Kos · #3

2η λύση

Η ακολουθία a_n

που ορίζεται αναδρομικά ως

$\displaystyle{a_{2n}=a_n \quad , \quad a_{2n+1}=a_n+1 \quad , \quad n \geq 1}$
και a_0=0

,

μετράει τον αριθμό των

στη δυική αναπαράσταση του

. Τότε:

$\displaystyle{\begin{aligned} \sum_{n=1}^{\infty} \frac{ {\rm pop}(n) }{n(n+1)} = \sum_{n = 1}^{\infty} \frac{a_n}{n(n+1)} &= \sum_{n=1}^{\infty} \frac{a_{2n}}{2n(2n+1)} + \sum_{n = 0}^{\infty} \frac{a_{2n+1}}{(2n+1)(2n+2)} \\ &= \sum_{n=1}^{\infty} \frac{a_{n}}{2n(2n+1)} + \sum_{n = 0}^{\infty} \frac{a_{n} + 1}{(2n+1)(2n+2)} \\ &= \frac{1}2 + \frac{1}2 \sum_{n = 1}^{\infty} \frac{a_n}{n(2n+1)} + \frac{1}2 \sum_{n=1}^{\infty} \frac{a_n}{(n+1)(2n+1)} + \frac{1}2 \sum_{n=1}^{\infty} \frac{1}{(n+1)(2n+1)} \\ &= \frac{1}2 + \frac{1}2 \sum_{n=1}^{\infty} a_n \left( \frac{1}{n(2n+1)} + \frac{1}{(n+1)(2n+1)} \right) + \frac{1}2 \sum_{n=1}^{\infty} \frac{1}{(n+1)(2n+1)} \\ &= \frac{1}2+ \frac{1}2 \sum_{n=1}^{\infty} \frac{a_n}{n(n+1)} + \frac{1}2\sum_{n=1}^{\infty} \frac{1}{(n+1)(2n+1)} \end{aligned} }$
και το αποτέλεσμα έπεται.

Tolaso J Kos · #4

3η λύση

Για $k \in \mathbb{N}$ , θεωρούμε τη συνάρτηση
$\displaystyle{\theta_k(n) = \left\{\begin{matrix} 1 & , & \text{if k-th bit of n is set} \\ 0 & , & \text{otherwise} \end{matrix}\right.}$
Τότε,

$\displaystyle{\sum_{n=1}^{\infty} \frac{{\rm pop}(n)}{n(n+1)} = \sum_{n=1}^{\infty}\sum_{k=0}^{\infty} \frac{\theta_k(n)}{n(n+1)} = \sum_{k=0}^{\infty}\sum_{n=1}^{\infty} \frac{\theta_k(n)}{n(n+1)}}$
Μπορούμε να κάνουμε την εναλλαγή στο διπλό άθροισμα αφού όλοι οι όροι είναι μη αρνητικοί. Παρατηρούμε επίσης ότι $\theta_k(n) = 1$ αν-ν $(2\ell+ 1)2^k \leq n < (2\ell+2)2^k$ για κάποιον $\ell \in \mathbb{N}$ . Συνεπώς,

$\displaystyle{\begin{aligned} \sum_{k=0}^{\infty}\sum_{\ell=0}^{\infty} \sum_{n=(2\ell+1)2^k}^{(2\ell+2)2^k-1} \frac{1}{n(n+1)} &= \sum_{k=0}^{\infty}\sum_{\ell=0}^{\infty} \left(\frac{1}{(2\ell+1)2^k} - \frac{1}{(2\ell+2)2^k}\right)\\ &= \left(\sum_{k=0}^{\infty}2^{-k}\right)\sum_{\ell=0}^{\infty} \left(\frac{1}{2\ell+1} - \frac{1}{2\ell+2}\right) \\ &= \frac{1}{1-2^{-1}}\log 2 \\ &= 2\log 2 \end{aligned}}$
Σημείωση: Ουσιαστικά αυτή είναι η λύση του Δημήτρη.

Σειρά pop

Σειρά pop

Re: Σειρά pop

Re: Σειρά pop

Re: Σειρά pop

Μέλη σε σύνδεση