Dimostrazione verità o falsità

[sara09]

Salve, mi aiutate a fare questo esercizio?

Sia $ f(n) = sum_(i = 1 ) ^n i^k $ , con k una qualsiasi costante intera positiva. Si dimostri per esteso la verità o falsità della seguente affermazione: $ f(n) = \Theta (n^{k+1}) $.

Io penso che se la sommatoria di i da 1 a n di i (somma dei primi n numeri naturali) come forma chiusa è (n(n+1))/2 che dà un theta $ (n^{2}) $, e sappiamo anche che la forma chiusa di sommatoria da $ i=1 $ a n di i al quadrato sia nella forma di theta $ (n^{3}) $ allora si può affermare che sia theta di $ (n^{k+1}) $.

Ma matematicamente non saprei dirlo come potrei fare ed inoltre è corretto?

Grazie

[megas_archon]

Esiste una forma chiusa che esprime \(f(n)\) come un polinomio in $n$: https://en.wikipedia.org/wiki/Faulhaber%27s_formula

Questo polinomio è monico di grado $k+1$.

[otta96]

Non c'è bisogno di quella formula, scrivi $n^(k+1)$ come somma telescopica di $n^(k+1)-(n-1)^(k+1)$ e smanetta un po'.

[sara09]

Non c'è bisogno di quella formula, scrivi $n^(k+1)$ come somma telescopica di $n(n^(k+1)-(n-1)^(k+1)) $ e smanetta un po'.

intendi fare i vari calcoli svolgendo questa: $ sum_(i = 1) ^n n^(k+1)-(n-1)^(k+1) $ ?

[otta96]

Ci deve essere la $i$ al posto della $n$, ma sì, è quello che intendevo.

[sara09]

Ci deve essere la $i$ al posto della $n$, ma sì, è quello che intendevo.

quindi cosi: $ sum_(i = 1) ^n i^(k+1)-(i-1)^(k+1) $ ?

[sara09]

Ci deve essere la $i$ al posto della $n$, ma sì, è quello che intendevo.

che poi risolvendola avrei:
$ sum_(i = 1) ^n i^(k)* i- sum_(i = 1) ^n(i-1)^k *(i-1) $

Poi come procedo?

[otta96]

Per praticità è meglio se la scrivi come $sum_(i =0)^(n-1)(i+1)^(k+1)-i^(k+1)$, poi svolgi i calcoli e usi l'induzione su $k$.

[sara09]

Per praticità è meglio se la scrivi come $sum_(i =0)^(n-1)(i+1)^(k+1)-i^(k+1)$, poi svolgi i calcoli e usi l'induzione su $k$.

Okay, quindi poi avrei la che questa $sum_(i =0)^(n-1)(i+1)^(k+1)-i^(k+1)$ diventa $sum_(i =0)^(n-1)(1)^(k+1)$ dove per induzione:

- caso base [$k=0$] —> se $k = 0$ Allora ho che $sum_(i =0)^(n-1)(1)^(1)$ dove questa è una serie geometria con ragione q che è uguale a $ (n-1)+1 = n$

- passo induttivo [$k>0$] —> se $k>0$ allora ho che $sum_(i =0)^(n-1)(1)^(k+1) = n$

Quindi è falso dire che $f(n) = (n^{k+1})$.

Non so se è giusto, non penso, puoi aiutarmi?

[apatriarca]

La sommatoria inizia con \(i=1\) e non da \(i=0\).

Non è poi chiaro che cosa tu stia cercando di fare. Perché quell'uno? Hai
\[ \sum_1^n i^{k} \neq \sum_0^{n-1} 1^{k} \]
Quindi il tuo passo base è
\[ \sum_1^n i^{0} = \sum_1^n 1 = n. \]
Il tuo passo induttivo a quel punto consiste nel partire da
\[ \sum_1^n i^{k+1} \]
e di cercare di riscriverlo in funzione della sommatoria per \(k\).

EDIT: Nota che non ti ho fornito un procedimento per risolverlo, ma solo corretto quello che c'era di sbagliato nel tuo procedimento e la ragione per cui ti veniva falso nonostante la proposizione è effettivamente vera come puoi osservare dal link sulla formula generale per questo tipo di sommatorie.