uniolympiads English

IMC 2002, Ημέρα 1, Θέμα 3

Let nn be a positive integer and let

ak=1(nk),bk=2k−n,for k=1,2,…,n.a_k = \frac{1}{\binom{n}{k}}, \quad b_k = 2^{k-n}, \quad \text{for } k = 1, 2, \dots, n.

Show that

a1−b11+a2−b22+⋯+an−bnn=0.(1)\frac{a_1 - b_1}{1} + \frac{a_2 - b_2}{2} + \dots + \frac{a_n - b_n}{n} = 0. \qquad (1)
Πρωτότυπο από το επίσημο PDFLet n be a positive integer and let a k = 1 n , b k = 2 k−n , f or k = 1, 2, . . . , n. k Show that a 1 − b 1 a 2 − b 2 a n − b n + + ··· + = 0. 1 2 n (1)

Η μεταγραφή συγκρίθηκε σύμβολο προς σύμβολο με το πρωτότυπο, όχι ακόμα από άνθρωπο.

Χρόνος σε αυτό το θέμα 0:00

Δούλεψε τουλάχιστον 45 λεπτά πριν ανοίξεις τη λύση.

Επίσημη λύση

Solution. Since k(nk)=n(n−1k−1)k\binom{n}{k}=n\binom{n-1}{k-1} for all k≥1k\ge1, (1) is equivalent to

2nn[1(n−10)+1(n−11)+⋯+1(n−1n−1)]=211+222+⋯+2nn.(2)\frac{2^n}{n}\left[\frac{1}{\binom{n-1}{0}}+\frac{1}{\binom{n-1}{1}}+\dots+\frac{1}{\binom{n-1}{n-1}}\right]=\frac{2^1}{1}+\frac{2^2}{2}+\dots+\frac{2^n}{n}.\tag{2}

We prove (2) by induction. For n=1n=1, both sides are equal to 2.

Assume that (2) holds for some nn. Let

xn=2nn[1(n−10)+1(n−11)+⋯+1(n−1n−1)];x_n=\frac{2^n}{n}\left[\frac{1}{\binom{n-1}{0}}+\frac{1}{\binom{n-1}{1}}+\dots+\frac{1}{\binom{n-1}{n-1}}\right];
then
xn+1=2n+1n+1∑k=0n1(nk)=2nn+1(1+∑k=0n−1(1(nk)+1(nk+1))+1)==2nn+1∑k=0n−1n−kn+k+1n(n−1k)+2n+1n+1=2nn∑k=0n−11(n−1k)+2n+1n+1=xn+2n+1n+1.\begin{aligned}x_{n+1}&=\frac{2^{n+1}}{n+1}\sum_{k=0}^{n}\frac{1}{\binom{n}{k}}=\frac{2^n}{n+1}\left(1+\sum_{k=0}^{n-1}\left(\frac{1}{\binom{n}{k}}+\frac{1}{\binom{n}{k+1}}\right)+1\right)=\\&=\frac{2^n}{n+1}\sum_{k=0}^{n-1}\frac{\frac{n-k}{n}+\frac{k+1}{n}}{\binom{n-1}{k}}+\frac{2^{n+1}}{n+1}=\frac{2^n}{n}\sum_{k=0}^{n-1}\frac{1}{\binom{n-1}{k}}+\frac{2^{n+1}}{n+1}=x_n+\frac{2^{n+1}}{n+1}.\end{aligned}
This implies (2) for n+1n+1.

Μεταγραφή από το επίσημο κείμενο λύσεων, σελίδα 2. Η μεταγραφή δεν έχει ελεγχθεί δεύτερη φορά· αν έχεις αμφιβολία, κοίτα το πρωτότυπο.

Θέμα αρχείου: η εκφώνηση είναι το επίσημο κείμενο (μεταγραμμένο, με το πρωτότυπο παραπάνω). Η ταξινόμηση ανά αντικείμενο και η δυσκολία εκτιμήθηκαν αυτόματα· υποδείξεις και λύση στα ελληνικά προστίθενται σταδιακά.

Πώς πήγε;