Somme de combinaisons

kouassi

Aidez-moi à démontrer par récurrence la formule suivante \[
\sum_{k=0}^n\binom{k+n}{k}2^{n-k}=2^{2n}\]

kouassi

Bonjour... j'ai manqué à la courtoisie ... désolé.

Math Coss

Eh bien, commence par mettre en place la récurrence : initialisation, mise en place de l'hérédité – ce que tu supposes, ce que tu veux démontrer, ce que tu as déjà fait, là où tu bloques.

Je suppose que le point clé, c'est de trouver une relation qui permet d'exprimer $\binom{k+n+1}{k}$ en fonction de coefficients binomiaux $\binom{k+n}{?}$. Connais-tu une telle formule ? Non, je reformule : tu connais une telle formule ; si elle t'échappe, voir (par exemple) https://fr.wikipedia.org/wiki/Coefficient_binomial.

kouassi

Voilà où j'en suis:
l'initialisation c'est trivial
l’hérédité c'est là que ça coince...
En supposant vrai la formule à l'ordre $n$ je veux montrer qu'elle est vrai aussi à l'ordre $n+1$
c'est-à-dire montrer que $\sum_{k=0}^{n+1}\binom{k+n+1}{k}2^{n+1-k}=2^{2n+2}$

En usant de la formule de Pascal: $\binom{k+n+1}{k}=\binom{k+n}{k}+\binom{k+n}{k-1}$ on obtient:

$\sum_{k=0}^{n+1}\binom{k+n+1}{k}2^{n+1-k}= \sum_{k=0}^{n+1}\binom{k+n}{k}2^{n+1-k} + \sum_{k=1}^{n+1}\binom{k+n}{k-1}2^{n+1-k}$

La première somme de droite par hypothèse de récurrence donne $2^{2n+1}+ \binom{2n+1}{n+1}$
pour la deuxième:

$\sum_{k=1}^{n+1}\binom{k+n}{k-1}2^{n+1-k}=\sum_{k=0}^{n}\binom{k+n+1}{k}2^{n-k}$


$ =\sum_{k=0}^{n}\binom{k+n}{k}2^{n-k}+ \sum_{k=1}^{n}\binom{k+n}{k-1}2^{n-k}$

$=2^{2n}+\sum_{k=1}^{n}\binom{k+n}{k-1}2^{n-k}$

C'est sur cette dernière somme que je bloque

babsgueye

Salut.

@kouassi, avec le début de ton raisonnement, je pense qu'il est plus facile d'utiliser la remarque:$$\sum_{k=0}^{k=n+1}\binom{k+n+1}{k}2^{n+1-k} = 2\times \sum_{k=0}^{k=n+1}\binom{k+n+1}{k}2^{n-k}$$ pour ensuite utiliser la formule de Pascal.

kouassi

Je ne vois pas en quoi c'est plus facile babsgueye je n'arrive toujours pas à calculer
$\sum_{k=0}^{k=n+1}\binom{k+n+1}{k}2^{n-k}$ puisque elle est égale à

$\sum_{k=0}^{k=n+1}\binom{k+n}{k}2^{n-k}+\sum_{k=1}^{k=n+1}\binom{k+n}{k-1}2^{n-k}$ et cela me redonne le résultat sur lequel je bloque donc je n'ai toujours pas avancé

babsgueye

Maintenant utilise l'idée de récurrence et n'oublie pas le $2$ qui est en facteur. À quoi sont égales ces deux sommes d'après l'hypothèse au rang $n$ ?

kouassi

La première somme vaut $2^{2n}+\binom{2n+1}{n+1}2^{-1}$ et la seconde je m'y prends comment ?

babsgueye

Remarque $\binom{n}{k} = 0$ si $k\lt 0$.

kouassi

ça je sais mais je ne vois vraiment pas

babsgueye

Ben j'avais un peu regardé tout ça mentalement. Dans ton second terme, je viens de voir que tu vas de $k=1$ donc tu as déjà utilisé ma remarque ci-dessus. Mais est ce la meilleur façon de faire ? Et si tu disais $\sum_{k=0}^{n+1}\binom{k+n}{k-1}2^{n-k} = \sum_{k=0}^{n+1}\binom{k+n+1}{k}2^{n-k-1} = 2^{-1}\sum_{k=0}^{n+1}\binom{k+n+1}{k}2^{n-k}$

kouassi

et si j'utilise le formule de pascal dans cette dernière j'obtiens une autre somme que je ne sais toujours pas calculer
tout ça ressemble à ce que j'ai déjà fait plus haut

babsgueye

J'ai itéré la formule que je t'ai donné et arrivé à une formule donnant $\binom{2n+1}{n+1}$ si ta formule initiale est vraie. Maintenant j'en doute. Vérifie la pour $n = 5$ ou une valeur plus petite, pour voir; parce que si elle est fausse on ne pourra effectivement pas la démontrer..

babsgueye

Ben j'ai vérifié jusqu'à $n=5$ et la formule est toujours vraie. Je pensais la récurrence élémentaire, c'est apparemment pas le cas. Je vais voir ça plus sérieusement ultérieurement.

kouassi

Si elle est bien juste et on y arrive voici la solution à laquelle j'aboutis par ton concours que je pense être juste:
Pour montrer que: \[\sum_{k=0}^{n+1}\binom{k+n+1}{k}2^{n+1-k}=2^{2n+2}\]
on remarque comme tu l'as dit babsgueye que: $\sum_{k=0}^{k=n+1}\binom{k+n+1}{k}2^{n+1-k} = 2\times \sum_{k=0}^{k=n+1}\binom{k+n+1}{k}2^{n-k}=2 \times S$

$S=\sum_{k=0}^{k=n+1}\binom{k+n+1}{k}2^{n-k}=\sum_{k=0}^{k=n+1}\binom{k+n}{k}2^{n-k}+\sum_{k=1}^{k=n+1}\binom{k+n}{k-1}2^{n-k}=S_1+S_2$

car $\binom{k+n+1}{k}=\binom{k+n}{k}+\binom{k+n}{k-1}$

Par suite $S_1=\sum_{k=0}^{k=n+1}\binom{k+n}{k}2^{n-k}=\sum_{k=0}^{k=n}\binom{k+n}{k}2^{n-k}+\binom{2n+1}{n+1}2^{-1}$

Et par HR: $\sum_{k=0}^{k=n}\binom{k+n}{k}2^{n-k}=2^{2n}$

CQFD et Merci à tous
Bonne soirée


d'où $\fbox{$S_1=2^{2n}+\binom{2n+1}{n+1}2^{-1}$}$


$S_2=\sum_{k=1}^{n+1}\binom{k+n}{k-1}2^{n-k} = \sum_{k=0}^{n}\binom{k+n+1}{k}2^{n-k-1} = 2^{-1}\sum_{k=0}^{n}\binom{k+n+1}{k}2^{n-k}$

$S_2=2^{-1}\left [ \sum_{k=0}^{n}\binom{k+n}{k}2^{n-k}+\sum_{k=1}^{n}\binom{k+n}{k-1}2^{n-k}\right ]$

$S_2=2^{-1}\left [ 2^{2n}+\sum_{k=1}^{n}\binom{k+n}{k-1}2^{n-k}\right ]$

Posons $A=\sum_{k=1}^{n}\binom{k+n}{k-1}2^{n-k}$ . Alors

$S_2=2^{-1}\left [ 2^{2n}+A\right ]$


Or $S_2=\sum_{k=1}^{n+1}\binom{k+n}{k-1}2^{n-k}$

$S_2=\sum_{k=1}^{n}\binom{k+n}{k-1}2^{n-k}+\binom{2n+1}{n}2^{-1}=A+\binom{2n+1}{n}2^{-1}$

Donc $2^{-1}\left [ 2^{2n}+A\right ]=A+\binom{2n+1}{n}2^{-1}$ et par suite

$A=2^{2n}-\binom{2n+1}{n}$ d'où

$\fbox{$S_2=2^{2n}-\binom{2n+1}{n}2^{-1}$}$


Ainsi $S=S_1+S_2=2^{2n+1}$

et pour finir \[\sum_{k=0}^{n+1}\binom{k+n+1}{k}2^{n+1-k}=2\times S=2^{2n+2}\]

babsgueye

@kouassi, il y a une coquille à la fin ($S_1$ contient le terme $\binom{2n+1}{n+1}2^{-1}$ alors que $S_2$ contient le terme $\binom{2n+1}{n}2^{-1}$; leur différence ne s'annule pas !), bizarrement, je ne vois pas où se trouve l'erreur ?

babsgueye

Ah ok, pardon @kaoussi. En fait $\binom{2n+1}{n+1} = \binom{2n+1}{n}$. Belle preuve !

Math Coss

Bien joué Kouassi !

kouassi

Merci