Sommare potenze

[Drago96]

Siano $n,k$ due interi positivi.
Determinare in funzione di $n$ e $k$ $$S(k,n)=k+2\cdot k^2+\dots+n\cdot k^n=\sum_{i=1}^n i\cdot k^i$$

E' facile, ma può essere utile per lavorare un po' sulle serie di potenze, aka generatrici (ovvio, si può fare con "trucchi normali" e non analitici)

[Lasker]

Sono impedito con generatrici (anche se non mi sembra di usarle, meglio i trucchi normali) e ho appena fatto un allenamento, non garantisco nulla sulla correttezza della soluzione .
Più che altro, io il problema lo vedrei come una sommatoria di serie geometriche:
$$k\sum_{i=0}^{n-1} {k^i}+k^2\sum_{i=0}^{n-2}{k^i}+...+k^n\sum_{i=0}^0 {k^i}$$
Dunque, usando la formula della serie geometrica, ottengo:
$$k\frac{k^{n}-1}{k-1}+k^2\frac{k^{n-1}-1}{k-1}+...+k^n\frac{k^1-1}{k-1}$$
Raccogliendo e sviluppando i conti, si ottiene:
$$\frac{k}{k-1}\left[(k^{n}-1)+(k^{n}-k)+...+(k^{n}-k^{n-1})\right]=\frac{k}{k-1}\left[nk^n-\frac{k^n-1}{k-1}\right]$$
Adesso dovrebbero esserci solo delle semplificazioni:
$$\sum_{i=1}^n i\cdot k^i=\frac{k}{k-1}\left(\frac{nk^{n+1}-(n+1)k^n+1}{k-1}\right)=\frac{nk^{n+2}-(n+1)k^{n+1}+k}{(k-1)^2}$$
Che dovrebbe essere giusta, a parte i casi $k=1$, in cui la formula è $\frac{n(n+1)}{2}$, ed $n=1$, in cui la formula è $k$.
EDIT: in realtà, per $n=1$ la formula funziona...

[Drago96]

Very good!
Chi tenta ora con le generatrici?

P.S: allenamento di cosa?

[Lasker]

OT: io faccio pallamano, uno sport talmente poco considerato in Italia che si arriva ai nazionali in quanto unica squadra del Friuli
(siamo in preparazione atletica ed è abbastanza massacrante xD)

[enrico_s]

Ora non ho voglia di scrivere la dimostrazione in latex anche perché sono con il cellulare..
Comunque la mia idea, dopo tanti tentativi, è stata di moltiplicare $ S $ per k
Poi faccio $ S-kS $ e si ottiene una nuova somma , poi con qualche raccoglimento si ottiene lo stesso risultato di Lasker

Domani magari la scrivo per bene

[Lasker]

Forse mi è venuto in mente un altro modo per fare il problema (somiglia abbastanza ad una funzione generatrice ), ricordando che:
$$\sum_{i=0}^{n-1} {(i+1)k^i}=S$$
è la derivata prima di:
$$\frac{k^{n+1}-1}{k-1}$$
Dunque, estraendo la derivata parziale rispetto a $k$ nell'ultima espressione (con le usuali regole: derivata di un rapporto...), ottengo:
$$S=\frac{-(n+1)k^n(k-1)-[1\cdot (k^{n+1}-1)]}{(k-1)^2}=\frac{nk^{n+1}-(n+1)k^n+1}{(k-1)^2}$$
Moltiplicando tutti i membri per $k$, ottengo proprio:
$$\sum_{i=1}^n {ik^i}=\frac{nk^{n+2}-(n+1)k^{n+1}+k}{(k-1)^2}$$
Che è lo stesso risultato di prima!

[arack]

Procedimento simile a quello degli altri:

\[S_n = \sum_{i=1}^n i \cdot k^i = S_{n-1} + n \cdot k^n\]
\[S_n = k + \sum_{i=2}^n i \cdot k^i = k + \sum_{i=1}^{n-1} (i+1) \cdot k^{i+1} = k + k\left(S_{n-1} + \sum_{i=1}^{n-1} k^i \right)\]
Da qui sostituisco \(S_{n-1}\) dalla prima equazione, metto in evidenza \(S_n\) e faccio un paio di somme per arrivare sempre allo stesso risultato.


Rilancio con una forse ancora più semplice:

Sia \(f_n\) l'ennesimo numero di fibonacci (aka. \(f_0 = 0\), \(f_1 = 1\), \(f_n = f_{n-1} + f_{n-2}\)), determinare in funzione di \(n\) ed \(x\)
\[ F_n(x) = \sum_{i = 0}^{n} f_i \cdot x^i\]
Fonte: projecteuler 435

[Triarii]

Proviamoci. Partiamo dagli ultimi termini
Sia $S(n) \sum_{k=0}^n f_kx^k$
$S(n)=S(n-1)+f_nx^n $
$S(n-1)=S(n-2)+f_{n-1}x^{n-1}$
Partiamo dai primi termini.
$S(n)=f_0+xf_1+\sum_{k=2}^n f_kx^k=f_0+f_1x+\sum_{k=0}^{n-2} f_{i+2}x^{i+2}=$
$=f_0+f_1+\sum_{k=0}^{n-2} f_{i+1}x^{i+2} +\sum_{k=0}^{n-2} f_ix^{i+2}$
$=f_0+f_1+xS(n-1)+f_0x++x^2S(n-2)$
Ora ci si esplicita ad esempio $ S(n-2) $ o $ S(n) $ (basta fare attenzione poi ai vari n in fondo ) e otteniamo $ S(n)= $$ \frac {f_{n+1}x^{n+1}(1-x)+f_{n+2}x^{n+2}-(f_0+f_1x+f_0x)} {x^2+x-1} $
che nel nostro caso diventa S(n)=$ \frac {f_{n+1}x^{n+1}(1-x)+f_{n+2}x^{n+2}-x} {x^2+x-1} $

[enrico_s]

allora intanto propongo la mia soluzione al primo problema

$ S=k+2k^2+3k^3+...+nk^n $
$ k\cdot S=k^2+2k^3+3k^4+...+nk^{n+1} $
$ S-kS=(1-k)S=k+k^2+k^3+...+k^n-nk^{n+1}=k\frac{k^n-1}{k-1}-nk^{n+1} $

$ (1-k)S=\frac{k^{n+1}-k-nk^{n+2}+nk^{n+1}}{k-1} $

$ S=\frac{k+nk^{n+2}-(n+1)k^{n+1}}{(k-1)^2} $

Per quanto riguarda il secondo problema , mi viene un risultato diverso da Triarii

Ho
$ F_n(x)=0+1x+1x^2+2x^3+3x^4+5x^5+...+f_nx^n $
$ xF_n(x)=0+1x^2+1x^3+2x^4+3x^5+...+f_{n-1}x^n+f_nx^{n+1} $

faccio la sottrazione tra queste due e ottengo
$ (1-x)F_n(x)=1x+1x^3+1x^4+2x^5+...+f_{n-2}x^n-f_nx^{n+1} $

divido quest'ultima per x e ottengo
$ (\frac{1-x}{x})F_n(x)=1+1x^2+1x^3+2x^4+3x^5...+f_{n-2}x^{n-1}-f_nx^n $

faccio $ xF_n(x)-(\frac{1-x}{x})F_n(x) $

$ (\frac{x^2+x-1}{x})F_n(x)=f_{n-1}x^n+f_nx^{n+1}-1+f_nx^n=f_{n+1}x^{n}+f_nx^{n+1}-1 $

quindi $ F_n(x)=\frac {f_{n+1}x^{n+1}+f_nx^{n+2}-x}{x^2+x-1} $

qualcuno sa dirmi dove sbaglio se la mia soluzione non è corretta?

[Triarii]

Ti viene diverso perchè ho sbagliato e ho modificato ora