Γεωμετρική πρόοδος

Η γεωμετρική πρόοδος $\alpha _{\nu }=3\cdot 2^{\nu -1}$.

Στα μαθηματικά, γεωμετρική πρόοδος είναι η ακολουθία $\alpha _{1},\alpha _{2},\ldots$, στην οποία για οποιουσδήποτε δύο διαδοχικούς όρους $\alpha _{\nu },\alpha _{\nu +1}$ ισχύει ότι $\alpha _{\nu +1}=\alpha _{\nu }\cdot \lambda$ για έναν σταθερό αριθμό $\lambda \neq 0$ και επιπλέον $\alpha _{1}\neq 0$. Ο αριθμός αυτός λέγεται ο λόγος της προόδου.

Ισοδύναμα, οι όροι μίας γεωμετρικής προόδου μπορούν να οριστούν με τον γενικό και τον αναδρομικό τύπο:

• Γενικός τύπος: $\alpha _{\nu }=\alpha _{1}\cdot \lambda ^{\nu -1}$, όπου ορίζεται ο $\nu$-οστός όρος συναρτήσει του πρώτου όρου και του λόγου.
• Αναδρομικός τύπος: $\alpha _{\nu +1}=\alpha _{\nu }\cdot \lambda$ για $\nu \geq 1$, όπου ορίζεται ο $\nu$-οστός όρος συναρτήσει του προηγούμενου όρου και του λόγου.

Για παράδειγμα, για $\alpha _{1}=3$ και $\lambda =2$, οι όροι της γεωμετρικής προόδου είναι

$\alpha _{1}=3,\alpha _{2}=6,\alpha _{3}=12,\alpha _{4}=24,\ldots$

και για $\alpha _{1}=2$ και $\lambda =-3$

$\alpha _{1}=2,\alpha _{2}=-6,\alpha _{3}=18,\alpha _{4}=-54,\ldots$

Η γεωμετρική πρόοδος ικανοποιεί την γραμμική αναδρομική σχέση πρώτου βαθμού με συντελεστή $\lambda$ και σταθερή όρο $0$.

Ισοδυναμία ορισμών

Γενικός σε αναδρομικό τύπο

Απόδειξη  

Ξεκινώντας από τον γενικό τύπο έχουμε ότι

$\alpha _{\nu +1}=\alpha _{1}\cdot \lambda ^{\nu }=(\alpha _{1}\cdot \lambda ^{\nu -1})\cdot \lambda =\alpha _{\nu }\cdot \lambda$,

και επομένως οδηγούμαστε στον αναδρομικό.

Αναδρομικός σε γενικό τύπο

Απόδειξη  

Για να αποδείξουμε τον γενικό τύπο από τον αναδρομικό, θα χρησιμοποιήσουμε την μέθοδο της μαθηματικής επαγωγής για όλους τους φυσικούς αριθμούς $\nu$.

Βασική Περίπτωση: Για $\nu =1$, έχουμε ότι $\alpha _{1}\cdot \lambda ^{\nu -1}=\alpha _{1}\cdot \lambda ^{1-1}=\alpha _{1}\cdot 1=\alpha _{1}$.

Επαγωγική Περίπτωση: Αν ισχύει για $\nu =\kappa$, δηλαδή $\alpha _{\kappa }=\alpha _{1}\cdot \lambda ^{\kappa -1}$, θα δείξουμε ότι ισχύει και για $\nu =\kappa +1$. Από τον αναδρομικό τύπο,

$\alpha _{\kappa +1}=\alpha _{\kappa }\cdot \lambda =\alpha _{1}\cdot \lambda ^{\kappa -1}\cdot \lambda =\alpha _{1}\cdot \lambda ^{\kappa }$.

Επομένως ισχύει και για $\nu =\kappa +1$ και έτσι για όλους τους φυσικούς αριθμούς $\nu$.

Ιδιότητες

Γραφική παράσταση

Η γραφική παράσταση της γεωμετρικής προόδου είναι σημεία

• μίας εκθετικής συνάρτησης, όταν $\lambda >0$ (και $\lambda \neq 1$),
• μίας σταθερής συνάρτησης όταν $\lambda =1$.
• δύο εκθετικών συναρτήσεων όπου η μία είναι η αντίθετη της άλλης, όταν $\lambda <0$,
• δύο σταθερών συναρτήσεων όταν $\lambda =-1$.

Παραδείγματα γραφικών παραστάσεων γεωμετρικής προόδου

Μίας εκθετικής συνάρτησης

Μίας σταθερής συνάρτησης

Δύο εκθετικών συναρτήσεων

Δύο σταθερών συναρτήσεων

Μονοτονία

Η ακολουθία είναι

• γνησίως αύξουσα όταν $\lambda >1$,
• σταθερή όταν $\lambda =1$,
• γνησίως φθίνουσα όταν $0<\lambda <1$.

Παραδείγματα προόδων διαφορετικής μονοτονίας

Γνησίως αύξουσα

Σταθερή

Γνησίως φθίνουσα

Άθροισμα πρώτων όρων

Για το άθροισμα $S_{\nu }=\alpha _{1}+\alpha _{2}+\ldots \alpha _{\nu }$ των $\nu$ πρώτων όρων της ακολουθίας έχουμε τις εξής περιπτώσεις:

• Αν $\lambda \neq 1$, τότε

$S_{\nu }=\alpha _{1}\cdot {\frac {\lambda ^{\nu }-1}{\lambda -1}}$

Απόδειξη  

Χρησιμοποιώντας τον γενικό τύπο $\alpha _{i}=\alpha _{1}\cdot \lambda ^{i-1}$ έχουμε ότι

$S_{\nu }=\alpha _{1}+\alpha _{1}\cdot \lambda +\ldots \alpha _{1}\cdot \lambda ^{\nu -1}$

και

$\lambda \cdot S_{\nu }=\alpha _{1}\cdot \lambda +\alpha _{1}\cdot \lambda ^{2}+\ldots \alpha _{1}\cdot \lambda ^{\nu }$.

Αφαιρώντας τις δύο παραπάνω σχέσεις κατά μέλη, έχουμε ότι

$\lambda \cdot S_{\nu }-S_{\nu }=-\alpha _{1}+(\alpha _{1}\cdot \lambda -\alpha _{1}\cdot \lambda )+\ldots (\alpha _{1}\cdot \lambda ^{\nu -1}-\alpha _{1}\cdot \lambda ^{\nu -1})+\alpha _{1}\cdot \lambda ^{\nu }$,

που είναι ισοδύναμο με

$(\lambda -1)S_{\nu }=\alpha _{1}\cdot (\lambda ^{\nu }-1)$.

Καθώς $\lambda \neq 1$, καταλήγουμε ότι

$S_{\nu }={\frac {\lambda ^{\nu }-1}{\lambda -1}}$.

• Αν $\lambda =1$,

$S_{\nu }=\nu \cdot \alpha _{1}$.

Απόδειξη  

Σε αυτή την περίπτωση όλοι οι όροι της γεωμετρικής προόδου είναι ίσοι μεταξύ τους και επομένως το άθροισμα $\nu$ όρων είναι $\nu \cdot \alpha _{1}$.

Σημείωση: Στην ειδική περίπτωση που $\lambda =-1$ η ακολουθία αποτελείται από όρους $\alpha _{1},-\alpha _{1},\alpha ,-\alpha _{1},\ldots$ και επομένως

$S_{\nu }={\begin{cases}\alpha _{1}&{\text{αν }}\nu {\text{ είναι μονός}},\\0&{\text{αν }}\nu {\text{ είναι ζυγός}}.\end{cases}}$

Γεωμετρική σειρά

Απεικόνιση του αθροίσματος των όρων μίας γεωμετρικής προόδου με $\lambda =1/2$, όπου το συνολικό εμβαδόν είναι ίσο με $2$.

Όταν $|\lambda |<1$, έχουμε ότι η γεωμετρική σειρά συγκλίνει, δηλαδή το όριο του αθροίσματος όλων των όρων της γεωμετρικής προόδου είναι πεπερασμένο. Πιο συγκεκριμένα,

$\sum _{i=1}^{\infty }\alpha _{i}={\frac {\alpha _{1}}{1-\lambda }}$

Απόδειξη  

Θα χρησιμοποιήσουμε ότι αφού $|\lambda |<1$, το όριο ${\textstyle \lim _{\nu \to \infty }\lambda ^{\nu }=0}$.

${\begin{aligned}\sum _{i=1}^{\infty }\alpha _{i}&=\lim _{\nu \to \infty }S_{\nu }\\&=\lim _{\nu \to \infty }\alpha _{1}\cdot {\frac {\lambda ^{\nu }-1}{\lambda -1}}\\&={\frac {\alpha _{1}}{\lambda -1}}\lim _{\nu \to \infty }(\lambda ^{\nu }-1)\\&={\frac {\alpha _{1}}{\lambda -1}}\cdot (-1)\\&={\frac {\alpha _{1}}{1-\lambda }}.\end{aligned}}$

Μέσος όρος

• Ο γεωμετρικός μέσος όρος δύο θετικών αριθμών $\alpha ,\gamma$ είναι ο $\beta$, αν και μόνο αν οι $\alpha ,\beta ,\gamma$ είναι διαδοχικοί όροι γεωμετρικής προόδου.

Απόδειξη  

($\Rightarrow$) Αν $\alpha ,\beta ,\gamma$ είναι διαδοχικοί όροι γεωμετρικής προόδου, τότε $\alpha =\alpha _{1}\cdot \lambda ^{\kappa }$, $\beta =\alpha _{1}\cdot \lambda ^{\kappa +1}$ και $\gamma =\alpha _{1}\cdot \lambda ^{\kappa +2}$, για κάποιους θετικούς αριθμούς $\alpha _{1},\lambda$ και για έναν θετικό ακέραιο $\kappa$. Επομένως,

${\sqrt {\alpha \gamma }}={\sqrt {\alpha _{1}\cdot \lambda ^{\kappa }\cdot \alpha _{1}\cdot \lambda ^{\kappa +2}}}{\sqrt {\alpha _{1}^{2}\cdot \lambda ^{2\kappa +2}}}=\alpha _{1}\cdot \lambda ^{\kappa }=\beta .$

($\Leftarrow$) Αν $\beta$ ο γεωμετρικός μέσος των $\alpha ,\gamma$ τότε

$\beta ={\sqrt {\alpha \gamma }}\Rightarrow {\frac {\beta }{\alpha }}={\frac {\gamma }{\beta }}.$

Έστω $\lambda =\beta /\alpha =\gamma /\beta$, τότε $\beta =\alpha \cdot \lambda$ και $\gamma =\beta \cdot \lambda =\alpha \cdot \lambda ^{2}$.

Συνεπώς, είναι όροι της γεωμετρικής προόδου με πρώτο όρο το $\alpha$ και λόγο $\lambda$.

Γινόμενο πρώτων όρων

Για το γινόμενο $\Pi _{\nu }$ των πρώτων $\nu$ όρων της ακολουθίας, έχουμε ότι

$\Pi _{\nu }=\alpha _{1}\cdot \alpha _{2}\cdot \ldots \cdot \alpha _{\nu }=\alpha _{1}^{\nu }\cdot \lambda ^{{\frac {1}{2}}\nu \cdot (\nu -1)}$

Απόδειξη  

Από τον γενικό τύπο έχουμε ότι

${\begin{aligned}\Pi _{\nu }&=\alpha _{1}\cdot \alpha _{2}\cdot \ldots \cdot \alpha _{\nu }\\&=\alpha _{1}\cdot (\alpha _{1}\cdot \lambda )\cdot \ldots (\alpha _{1}\cdot \lambda ^{\nu -1})\\&=\alpha _{1}^{\nu }\cdot \lambda ^{1+2+\ldots +(\nu -1)}\\&=\alpha _{1}^{\nu }\cdot \lambda ^{{\frac {1}{2}}\nu \cdot (\nu -1)},\end{aligned}}$

όπου χρησιμοποιήσαμε το άθροισμα της αριθμητικής προόδου

$1+2+\ldots +(\nu -1)={\tfrac {1}{2}}\nu \cdot (\nu -1)$.

Σχέση με άλλες ακολουθίες

• Αν $(\alpha _{\nu })_{\nu =1}^{\infty }$ είναι μία γεωμετρική πρόοδος με $\alpha _{\nu }>0$ και λόγο $\lambda$, τότε η ακολουθία $\beta _{\nu }=\log \alpha _{\nu }$ είναι αριθμητική πρόοδος με διαφορά $\omega =\log \lambda$, καθώς $\beta _{\nu }=\log \alpha _{\nu }=\log(\alpha _{1}\lambda ^{\nu -1})=\log \alpha _{1}+(\nu -1)\cdot \log \lambda$.

Υπολογισμός

Ο παρακάτω κώδικας στην γλώσσα προγραμματισμού C++ χρησιμοποιεί τον αναδρομικό τύπο ώστε να τυπώσει τους πρώτους πέντε όρους της προόδου

#include <iostream>

int main() {
   double a_1 = 2.0;
   double lambda = 3.0;
   
   double a_n = a_1;
   for (int n = 1; n <= 5; ++n) {
     std::cout << "a_" << n << " = " << a_n << ", ";
     a_n = a_n * lambda; // Υπολογισμός επόμενου όρου.
   }
   return 0;
}
/* Τυπώνει: a_1 = 2, a_2 = 6, a_3 = 18, a_4 = 54, a_5 = 162, */

Ο παρακάτω κώδικας χρησιμοποιεί τον γενικό τύπο ώστε να υπολογίσει έναν συγκεκριμένο όρο της ακολουθίας. Χρησιμοποιεί σταθερό αριθμό πράξεων (και λογαριθμικό πλήθος πολλαπλασιασμών).

double geometric_nth(double a1, double lambda, int n) {
   return a1 * std::pow(lambda, (n - 1));
}

Ο αναδρομικός τύπος είναι πιο αργός καθώς χρειάζεται γραμμικό αριθμό πράξεων, δηλαδή $\Theta (n)$ πράξεις.

double geometric_nth_recursive(double a1, double lambda, int n) {
   if (n == 1) return a1;
   return lambda * geometric_nth_recursive(a1, lambda, n-1);
}

Εφαρμογές

Θεωρία πιθανοτήτων

Έστω ότι έχουμε ένα κέρμα που με πιθανότητα $p$ είναι κορώνα και με πιθανότητα $1-p$ είναι γράμματα. Αν $X$ είναι το πλήθος των φορών που πρέπει να ρίξουμε το κέρμα μέχρι να δούμε για πρώτη φορά κορώνα, τότε

$\Pr(X=k)=(1-p)^{k-1}\cdot p$,

δηλαδή οι όροι της συνάρτησης μάζας πιθανότητας είναι όροι μίας γεωμετρικής προόδου.

Στην θεωρία πιθανοτήτων, μία τέτοια τυχαία μεταβλητή λέγεται ότι ακολουθεί την γεωμετρική κατανομή .

Ανάλυση αλγορίθμων

Συχνά στην ανάλυση αλγορίθμων διάφορες ποσότητες είναι ίσες με το άθροισμα των όρων μίας γεωμετρικής προόδου (συνηθέστερα της $2^{0},2^{1},2^{2},\ldots$. Για παράδειγμα,

• στην ανάλυση της μνήμης που χρησιμοποιεί ο αλγόριθμος Hirschberg για την αντιστοίχιση βιολογικών ακολουθιών,
• στην συνολική πολυπλοκότητα στους δυναμικούς πίνακες,
• στην ανάλυση της μνήμης για την αναπαράσταση ενός πλήρους δυαδικού δέντρου.

Δείτε επίσης

• Γεωμετρικός μέσος
• Αριθμητική πρόοδος
• Μικτή πρόοδος