Dimostrazione verità o falsità
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
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
Risposte
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$.
Questo polinomio è monico di grado $k+1$.
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'.
"otta96":
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) $ ?
Ci deve essere la $i$ al posto della $n$, ma sì, è quello che intendevo.
"otta96":
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":[/quote]
[quote="otta96"]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?
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$.
"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$.
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?
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.
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.
"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.
Va bene grazie, quindi ora scrivere ciò \[ \sum_1^n i^{k+1} \] in funzione della sommatoria per \(k\) come dovrei fare? Nel senso posso trasformarla in \[ \sum_1^n i^{k}*i \] dove $i<= \sum_1^n i^{k}*i <= i/{(1-i)^2}$ dunque la $\sum_1^n i^{k}*i = i/(1+i^2-2i)$ ma poi come vado avanti arrivando ad avere $n^{k+1}$?
Grazie mille ☺️
"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.
Come scrivo la sommatoria in funzione di k ?
Riparti dal mio suggerimento, sviluppa $sum_(i =0)^(n-1)(i+1)^(k+1)-i^(k+1)$, che non fa $1$....
"otta96":
Riparti dal mio suggerimento, sviluppa $sum_(i =0)^(n-1)(i+1)^(k+1)-i^(k+1)$, che non fa $1$....
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=1 & i= 1$] —> 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>1 & i>1 $] —> allora ho che $sum_(i =0)^(n-1)(i)^(k+1) = ((i^{n-1}+1)/(i-1))$
Poi come faccio ad avere $n^{k+1}$ ?
Il problema di questa sommatoria è che richiede l'uso di qualche "trucco" non immediatamente ovvio o strumenti più avanzati per la sua soluzione.
Il trucco consiste nel considerare la differenza tra addendi successivi della sommatoria. Differenza che non è certamente uguale a \(1\) come hai scritto nella tua soluzione. Considera infatti per esempio il caso in cui \(k=1\) e \(i=5\). Hai che \(6^2 = 36\) e \(5^2 = 25\) per cui la loro differenza è \(11\) che è certamente diverso da \(1\)... Devi sviluppare il termine \((i+1)^{k+1}\) usando la formula per la potenza di un binomio che hai sicuramente visto nelle scuole superiori.
Il trucco consiste nel considerare la differenza tra addendi successivi della sommatoria. Differenza che non è certamente uguale a \(1\) come hai scritto nella tua soluzione. Considera infatti per esempio il caso in cui \(k=1\) e \(i=5\). Hai che \(6^2 = 36\) e \(5^2 = 25\) per cui la loro differenza è \(11\) che è certamente diverso da \(1\)... Devi sviluppare il termine \((i+1)^{k+1}\) usando la formula per la potenza di un binomio che hai sicuramente visto nelle scuole superiori.
La formula sarebbe la seguente:
\[ (x + y)^n = \sum_{k=0}^n \binom{n}{k}\,x^{k}\,y^{n-k} \]
Nel tuo caso hai \((i + 1)^{k+1}\) da cui si ottiene
\[ (i + 1)^{k+1} = \sum_{j=0}^{k+1} \binom{k+1}{j}\,i^{j}. \]
Se rimuovi \(i^{k+1}\) rimane tutto tranne il termine più grande:
\[ (i + 1)^{k+1} - i^{k+1} = \sum_{j=0}^{k} \binom{k+1}{j}\,i^{j}. \]
\[ (x + y)^n = \sum_{k=0}^n \binom{n}{k}\,x^{k}\,y^{n-k} \]
Nel tuo caso hai \((i + 1)^{k+1}\) da cui si ottiene
\[ (i + 1)^{k+1} = \sum_{j=0}^{k+1} \binom{k+1}{j}\,i^{j}. \]
Se rimuovi \(i^{k+1}\) rimane tutto tranne il termine più grande:
\[ (i + 1)^{k+1} - i^{k+1} = \sum_{j=0}^{k} \binom{k+1}{j}\,i^{j}. \]
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo