Relation de récurrence de la somme binomiale.

Question

J'essaye de trouver une solution de forme fermée à la somme $$ a(n):= \sum_{k=0}^{\lfloor n/3 \rfloor} \binom{n}{3k}. $$

Dans ma tentative, j'ai trouvé les premières valeurs de $a(n)$et les a saisis dans l'OEIS et a obtenu un succès pour la séquence A024493. Dans les notes, j'ai vu qu'il y avait une relation de récurrence donnée, à savoir$$ a(n) = 3a(n-1)-3a(n-2)+2a(n-3) $$ ou peut-être plus éclairant $$ a(n)-3a(n-1)+3a(n-2)-a(n-3) = a(n-3) $$ où nous pouvons voir que les coefficients du côté droit sont $(-1)^i \binom{3}{i}$ pour $0\leq i \leq 3$.

J'ai essayé de prouver cette relation par induction, mais le résultat semble dépendre de la valeur de $n\mod 3$ plus que sur les termes précédents.

Toute réflexion sur la façon dont je peux le prouver $a(n)$ satisfait la récursion donnée?

Answer 1

Par théorème binomial:

$$(1+x)^n={n \choose 0}+ {n \choose 1} x+ {n \choose 2} x^2+{ n\choose 3} x^3+{n \choose 4} x^4+....+{n \choose n}x^n~~~~(1)$$ Laissez-nous mettre $x=1,w,w^2$ whgere $w$ est la racine cubique de l'unité telle que $w^3=1$ et $1+w+w^2=0$. On a$$2^n={n \choose 0}+ {n \choose 1} + {n \choose 2}+{ n\choose 3}+{n \choose 4}+....+{n \choose n}.~~~~(2)$$ $$(1+w)^n={n \choose 0}+ {n \choose 1} w+ {n \choose 2} w^2+{ n\choose 3} w^3+{n \choose 4} w^4+....+{n \choose n}w^n~~~~(3)$$ $$(1+w^2)^n={n \choose 0}+ {n \choose 1}w^2 + {n \choose 2} w+{ n\choose 3}w^6+{n \choose 4}w^2+....+{n \choose n}w^{2n}.~~~~(4)$$ Ajouter (1-3) et chanter la propriété qui $1+w+w^2=0$, on a $$A_n=\sum_{k=0}^{[n/3]} {n \choose 3k}=\frac{1}{3}(2^n+(-1)^n[e^{4i\pi n/3}+e^{2i\pi n/3}])=\frac{1}{3}[2^n+2\cos(\pi n/3)]$$ On peut vérifier que les deux $2^n$ et $\cos(\pi n/3)$ tous deux combinés ou séparément satisfont à la relation de récurrence revendiquée qui $$A_n-3A_{n-1}+3A_{n-2}-2A_{n-3}=0,$$ car $-3A_{n-1}+3A_{n-2}=-3\cos(n \pi/3)$ et $A_n-2A_{n-3}=3 \cos (n\pi/3)$

Answer 2

Gardant à l'esprit que pour $ k > n$ ou $ k < 0$, ${ n \choose k } =0 $, nous pouvons écrire $a_n = \sum_{k= - \infty } ^\infty { n \choose 3k}$. Cela nous permet d'éviter le "avoir à considérer$n \pmod{3}$ cas ".

Ensuite, utilisez l'identité $ { n\choose k } = { n-1 \choose k-1 } + { n - 1 \choose k }$ (ce qui est toujours vrai quand $k > n$ ou $k < 0$) pour réduire itérativement $a_n - 3 a_{n-1} + 3a_{n-2} + 2 a_{n-3}$, C'EST À DIRE

$= \left[ \sum_{k} { n \choose 3k} \right] - 3 a_{n-1} + 3a_{n-2} - 2 a_{n-3} $
$ = \left[ \sum_{k} { n-1 \choose 3k-1} + {n-1 \choose 3k }\right] - 3 a_{n-1} + 3a_{n-2} - 2 a_{n-3}$
$ = \left[ \sum_{k} { n-1 \choose 3k-1} - 2 {n-1 \choose 3k }\right] + 3a_{n-2} - 2 a_{n-3}$
$ = \ldots $

Pouvez-vous compléter ceci pour montrer qu'il est égal à 0?

Answer 3

L'huile de serpent découvre et prouve simultanément la récidive: \begin{align} \sum_{n \ge 0} a_n z^n &=\sum_{n \ge 0} \sum_{k=0}^{\lfloor n/3 \rfloor} \binom{n}{3k} z^n \\ &= \sum_{k\ge 0} \sum_{n \ge 3k} \binom{n}{3k} z^n \\ &= \sum_{k\ge 0} \frac{z^{3k}}{(1-z)^{3k+1}} \\ &= \frac{1}{(1-z)} \sum_{k\ge 0} \left[\left(\frac{z}{1-z}\right)^3\right]^k \\ &= \frac{1}{(1-z)} \cdot \frac{1}{1-\left(\frac{z}{1-z}\right)^3} \\ &= \frac{(1 - z)^2}{(1 - 2 z) (1 -z + z^2)} \\ &= \frac{(1 - z)^2}{1 - 3 z + 3 z^2 - 2 z^3} \end{align} Le dénominateur implique immédiatement que $$a_n=3 a_{n-1} - 3 a_{n-2} + 2 a_{n-3}.$$