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

right|thumb|400px|Η γεωμετρική πρόοδος <math>\alpha_\nu = 3 \cdot 2^{\nu - 1}</math>.
Στα μαθηματικά, **γεωμετρική πρόοδος** είναι η ακολουθία \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.

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

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

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

## Ιδιότητες

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

### Μονοτονία
Η ακολουθία είναι 
* γνησίως αύξουσα όταν \lambda > 1,
* σταθερή όταν \lambda = 1,
* γνησίως φθίνουσα όταν 0 .

### Άθροισμα πρώτων όρων
Για το άθροισμα S_{\nu} = \alpha_1 + \alpha_2 + \ldots \alpha_\nu των \nu πρώτων όρων της ακολουθίας έχουμε τις εξής περιπτώσεις:
*Αν \lambda \neq 1, τότε
::S_\nu = \alpha_1 \cdot \frac{\lambda^{\nu}-1}{\lambda-1}

*Αν \lambda = 1, 
::S_\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}

### Γεωμετρική σειρά
thumb|200px|Απεικόνιση του αθροίσματος των όρων μίας γεωμετρικής προόδου με <math>\lambda=1/2</math>, όπου το συνολικό εμβαδόν είναι ίσο με <math>2</math>.

Όταν |\lambda| , έχουμε ότι η γεωμετρική σειρά συγκλίνει, δηλαδή το όριο του αθροίσματος όλων των όρων της γεωμετρικής προόδου είναι πεπερασμένο. Πιο συγκεκριμένα, 
:\sum_{i = 1}^{\infty} \alpha_i = \frac{\alpha_1}{1-\lambda}

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

\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)}

## Σχέση με άλλες ακολουθίες
* Αν (\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++ χρησιμοποιεί τον αναδρομικό τύπο ώστε να τυπώσει τους πρώτους πέντε όρους της προόδου


```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, */
```


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

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

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

```c++
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 για την αντιστοίχιση βιολογικών ακολουθιών,
* στην συνολική πολυπλοκότητα στους δυναμικούς πίνακες,
* στην ανάλυση της μνήμης για την αναπαράσταση ενός πλήρους δυαδικού δέντρου.

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

## Παραπομπές


Κατηγορία:Ακολουθίες