Filtriamo insieme

[Rho33]

Il valore della somma

$\displaystyle\sum_{i=0}^{33}\binom {99}{3i}$ può essere espresso nella forma $\dfrac {a^b+c}{d}$ . Trovare $a+b+c+d$


Bonus: Generalizzare con $n,k \in \mathbb{N}$ generici. Cioè, cosa posso dire del valore della somma:

$\displaystyle\sum_{i=0}^{n}\binom {n}{ki}$ con $n,k$ fissati ?



P.S. Per completezza $\displaystyle\binom {n}{k}=0$ per $k>n$

Hint per il bonus:

Testo nascosto:

Il problema è equivalente a trovare il numero di sottoinsiemi di $A= \{1,2,...,n \} $ il cui numero di elementi è divisibile per $k$

[carlotheboss]

O ho capito male il problema generale oppure è il numero di elementi del sottoinsieme ad essere divisibile per $k$ (e non la loro somma) perché sui casi piccoli non torna D:
Comunque il caso "piccolo" dovrebbe uscire $\dfrac{2^{99}-2}{3}$ per induzione (che non riesco a fare funzionare sul bonus)

[carlotheboss]

O ho capito male il problema generale oppure è il numero di elementi del sottoinsieme ad essere divisibile per $k$ (e non la loro somma) perché sui casi piccoli non torna D:

Mi spiego meglio, ad esempio se scelgo $n = k = 4$ il problema mi chiede di calcolare $\binom{4}{0} + \binom{4}{4} = 2$ mentre se considero $A = \{1, 2, 3, 4\}$ posso scegliere 3 sottoinsiemi tali che la loro somma è divisibile per $4$ (cioé $k$): $\{4\}$, $\{1, 3\}$, $\{1, 3, 4\}$ (oppure 4 se considero l'insieme vuoto).

[mr96]

L'hintone sta nel titolo, ma se non si conosce la teoria non aiuta molto...

[carlotheboss]

Purtroppo non penso di conoscerla essendo uno "nuovo", potresti dirmi di cosa si tratta precisamente?

[Rho33]

Sì, ora edito, intendo il numero di elementi divisibile per $k$! Ok, il caso piccolo e semplice va bene, anche se, come suggerisce mr96, c'è una soluzione molto molto molto più figa che ovviamente si generalizza. Anche io ho scoperto sta cosa da poco, che ti pare! Comunque il problema lo lascio ancora per un po' in caso qualcuno sia interessato

Come hint 1:

Testo nascosto:

come si calcola la somma dei coefficienti di un polinomio ?

Hint 2:

Testo nascosto:

e la somma dei coefficienti di grado pari?

Hint 3:

Testo nascosto:

Ora la parte più difficile, trova la somma dei coefficienti con esponente multiplo di $3$ e generalizza.