Προβλήματα Μαθηματικών

Μαΐου 4, 2008

Υπολογίστε το άθροισμα

Filed under: Λυμένα Προβλήματα — Mihalis Kolountzakis @ 5:46 μμ

Βρείτε ένα τύπο για το άθροισμα

\displaystyle \sum_{3 | k} {n \choose k}.

Advertisements

4 Σχόλια »

  1. Έστω s_n το ζητούμενο άθροισμα.
    Ορίζουμε την ακολουθία a_n για την οποία
    a_n=1 αν n\equiv 0 (mod 6),
    a_n=-1 αν n\equiv 3 (mod 6) και
    a_n=0 αν n\not\equiv 0 (mod 3).

    Ισχύει ότι
    \displaystyle s_n=\sum_{k=0}^n(-1)^k{n\choose k}a_k.

    Η γεννήτρια συνάρτηση της a_n είναι η
    f(x)=\frac{1}{1+x^3},
    άρα η γεννήτρια συνάρτηση της s_n είναι η
    g(x)=\frac{1}{1-x}\cdot f(\frac{-x}{1-x})=-\frac{(x-1)^2}{2x^3-3x^2+3x-1}=

    =\frac{1}{3}\cdot\left(\frac{1}{1-2x}+\frac{2-x}{1-x+x^2}\right)=

    =\frac{1}{3}\cdot\left(\frac{1}{1-2x}+\frac{2+x-x^2-2x^3-x^4+x^5}{1-x^6}\right).

    Τώρα παρατηρούμε ότι η \frac{1}{1-2x} είναι η γεννήτρια συνάρτηση της ακολουθίας 2^n και η \frac{2+x-x^2-2x^3-x^4+x^5}{1-x^6} είναι η γεννήτρια συνάρτηση της u_n που ορίζεται ως
    u_n=2,1,-1,-2,-1 ή 1 αν αντίστοιχα n\equiv 0,1,\cdots ή 5 (mod 6).

    Συνεπώς ισχύει ότι s_n=\frac{2^n+u_n}{3}.

    Μου αρέσει!

    Σχόλιο από steliosdes — Μαΐου 8, 2008 @ 12:54 πμ

  2. Ενδιαφέρουσα λύση που δεν την είχα υπόψιν. Παρατηρείστε ότι στο τελικό αποτέλεσμα φαίνεται καθαρά ότι το άθροισμα για k|3 είναι περίπου το 1/3 του όλου αθροίσματος (για όλα τα k).

    Ας κάνω και μια υπόδειξη για μια άλλη λύση (θα είναι ενδιαφέρον να συγκριθούν οι δύο τύποι στο τέλος).

    Χρησιμοποιείστε το διωνυμικό θεώρημα

    (1+x)^n = \sum_{k=0}^n {n \choose k} x^k

    για x = 1, \omega, \omega^2, όπου \omega=e^{2\pi i /3} είναι μια πρωταρχική κυβική ρίζα της μονάδας. Προσθέστε και χρησιμοποιείστε την ισότητα

    1+\omega+\omega^2 = 0.

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Μαΐου 8, 2008 @ 9:02 πμ

  3. Μια ακόμη λύση, όχι τόσο ωραία όσο οι άλλες δύο.
    Χρησιμοποιήστε τη συνδυαστική ταυτότητα
    {n+1\choose k}={n\choose k}+{n\choose k-1}
    για να γράψετε
    {n\choose k}+{n\choose k-1}+{n\choose k-2}={n+2\choose k}-{n+1\choose k}+{n\choose k}.
    Προσθέτοντας σε 3|k θα πάρουμε μια γραμμική αναδρομική εξίσωση για την ποσότητα που θέλουμε να υπολογίσουμε που μπορεί να λυθεί εύκολα.

    Μου αρέσει!

    Σχόλιο από loulakis — Μαΐου 8, 2008 @ 8:30 μμ

  4. Συγγνώμη για το λάθος στον κώδικα. Οι σχέσεις που δεν φαίνονται είναι
    {n+1\choose k}={n\choose k}+{n\choose k-1}
    και
    {n\choose k}+{n\choose k-1}+{n\choose k-2}={n+2\choose k}-{n+1\choose k}+{n\choose k}

    Μου αρέσει!

    Σχόλιο από loulakis — Μαΐου 8, 2008 @ 8:39 μμ


RSS feed for comments on this post. TrackBack URI

Σχολιάστε

Συνδεθείτε για να δημοσιεύσετε το σχόλιο σας:

Λογότυπο WordPress.com

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό WordPress.com. Αποσύνδεση / Αλλαγή )

Φωτογραφία Twitter

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Twitter. Αποσύνδεση / Αλλαγή )

Φωτογραφία Facebook

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Facebook. Αποσύνδεση / Αλλαγή )

Φωτογραφία Google+

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Google+. Αποσύνδεση / Αλλαγή )

Σύνδεση με %s

Blog στο WordPress.com.

Αρέσει σε %d bloggers: