Αρμονική πρόοδος

Στα μαθηματικά, αρμονική πρόοδος είναι η ακολουθία με μη-μηδενικούς όρους $\alpha _{1},\alpha _{2},\alpha _{3},\ldots$, στην οποία η διαφορά των αντιστρόφων δύο οποιοιδήποτε διαδοχικών της όρων $\alpha _{\nu },\alpha _{\nu +1}$ είναι σταθερή, δηλαδή

${\frac {1}{\alpha _{\nu +1}}}-{\frac {1}{\alpha _{\nu }}}=\omega$,

για μία τιμή $\omega$ που δεν εξαρτάται από τον δείκτη $\nu$.

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

• Γενικός τύπος: $\alpha _{\nu }={\frac {1}{{\frac {1}{\alpha _{1}}}+(\nu -1)\cdot \omega }}$.
• Αναδρομικός τύπος: $\alpha _{\nu +1}={\frac {1}{\omega +{\frac {1}{\alpha _{\nu }}}}}$.

Παραδείγματα

• (Αρμονικοί αριθμοί) Για $\alpha _{1}=1$ και $\omega =1$, λαμβάνουμε τους αρμονικούς αριθμούς, δηλαδή

$\alpha _{1}=1,\alpha _{2}={\frac {1}{2}},\alpha _{3}={\frac {1}{3}},\ldots$

• Για $\alpha _{1}=1$ και $\omega =2$, λαμβάνουμε τους

$\alpha _{1}=1,\alpha _{2}={\frac {1}{3}},\alpha _{3}={\frac {1}{5}},\ldots$,

δηλαδή τους αντίστροφους των περιττών αριθμών.

• Για $\alpha _{1}=-1/5$, $\omega =2$, η πρόοδος έχει αρχικά αρνητικού όρους (που μειώνονται) και μετά θετικούς (που επίσης μειώνονται),

$\alpha _{1}=-{\frac {1}{5}},\alpha _{2}=-{\frac {1}{3}},\alpha _{3}=-1,\alpha _{4}={\frac {1}{3}},\alpha _{5}=-{\frac {1}{5}}\ldots$.

• (Σταθερή ακολουθία) Όταν $\omega =0$, έχουμε την σταθερή ακολουθία, $\alpha _{1}=\alpha _{2}=\alpha _{3}=\ldots$.

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

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

Απόδειξη  

Από τον γενικό τύπο για τον $\nu$-οστό όρο έχουμε ότι

$\alpha _{\nu }={\frac {1}{{\frac {1}{\alpha _{1}}}+\nu \cdot \omega }}$.

Για τον $(\nu +1)$-οστό, έχουμε

${\begin{aligned}\alpha _{\nu +1}&={\frac {1}{{\frac {1}{\alpha _{1}}}+(\nu +1)\cdot \omega }}\\&={\frac {1}{{\frac {1}{\alpha _{1}}}+\nu \cdot \omega +\omega }}\\&={\frac {1}{{\frac {1}{\alpha _{\nu }}}+\omega }},\end{aligned}}$

που μας δίνει τον αναδρομικό τύπο.

Αναδρομικός σε σταθερή διαφορά

Απόδειξη  

Ο αναδρομικός τύπος για $\nu >1$ δίνει

$\alpha _{\nu }={\frac {1}{\omega +{\frac {1}{\alpha _{\nu -1}}}}}$.

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

${\frac {1}{\alpha _{\nu }}}-{\frac {1}{\alpha _{\nu -1}}}=\omega +{\frac {1}{\alpha _{\nu -1}}}-\alpha _{\nu -1}=\omega$,

που είναι μία σταθερή τιμή.

Σταθερή διαφορά σε γενικό τύπο

Απόδειξη  

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

Βασική Περίπτωση: Για $\nu =1$, έχουμε ότι

${\frac {1}{\alpha _{1}+(\nu -1)\cdot \omega }}=\alpha _{1}+(1-1)\cdot \omega =\alpha _{1}$.

Επαγωγική Περίπτωση: Αν ισχύει για $\nu =\kappa$, δηλαδή

$\alpha _{\kappa }={\frac {1}{\alpha _{1}+(\kappa -1)\cdot \omega }}$,

θα δείξουμε ότι ισχύει και για $\nu =\kappa +1$. Από τον αναδρομικό τύπο,

$\alpha _{\kappa +1}={\frac {1}{{\frac {1}{\alpha _{\kappa }}}+\omega }}=\alpha _{1}+(\kappa -1)\cdot \omega +\omega =\alpha _{1}+\kappa \cdot \omega$.

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

Ιδιότητες

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

Αρμονικές πρόοδοι για διάφορες τιμές του αρχικού όρου και της διαφοράς.

• Η γραφική παράσταση της αρμονικής προόδου είναι διαδοχικά σημεία ενός κλάδου δίκλαδης υπερβολής με κέντρο συμμετρίας την αρχή των αξόνων, η οποία όμως έχει μετατοπιστεί οριζόντια κατά $1-{\frac {1}{\omega a_{1}}}$.

Αρμονικός μέσος

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

Απόδειξη  

Έχουμε ότι οι $\alpha ,\beta ,\gamma$ είναι διαδοχικοί όροι μίας αρμονικής προόδου ανν

${\begin{aligned}{\frac {1}{\beta }}-{\frac {1}{\alpha }}&={\frac {1}{\gamma }}-{\frac {1}{\alpha }}\Leftrightarrow \\{\frac {2}{\beta }}&={\frac {1}{\alpha }}+{\frac {1}{\gamma }}\Leftrightarrow \\\beta &={\frac {2}{{\frac {1}{\alpha }}+{\frac {1}{\gamma }}}},\end{aligned}}$

που ισχύει ανν το $\beta$ είναι ο αρμονικός μέσος των $\alpha ,\gamma$.

Σχέση με αριθμητική πρόοδο

Οι αντίστροφοι των όρων μίας αρμονικής προόδου ορίζουν μία αριθμητική πρόοδο.

Απόδειξη  

Από τον γενικό τύπο προκύπτει ότι η ακολουθία $\beta _{\nu }=1/\alpha _{\nu }$ έχει γενικό τύπο

$\beta _{\nu }={\frac {1}{\alpha _{1}}}+(\nu -1)\omega$,

που είναι μία αριθμητική πρόοδος με πρώτο όρο το ${\frac {1}{\alpha _{1}}}$ και σταθερή διαφορά $\omega$.

Απόκλιση σειράς

Για οποιεσδήποτε τιμές των $\alpha _{1}$ και $\omega$ το άθροισμα των όρων της αρμονικής προόδου αποκλίνει, δηλαδή τείνει στο $+\infty$ (αν $\omega >0$_ ή στο $-\infty$ (αν $\omega <0$).

Απόδειξη  

Ξεκινάμε δείχνοντας ότι αυτό ισχύει για την αρμονική σειρά $\alpha _{\nu }=1/\nu$. Ξεκινάμε ομαδοποιώντας τους όρους στην πλησιέστερη μεγαλύτερη δύναμη του 2 ως εξης

${\begin{aligned}\sum _{i=1}^{\nu }{\frac {1}{i}}&=1+{\frac {1}{2}}+\left({\frac {1}{3}}+{\frac {1}{4}}\right)+\left({\frac {1}{5}}+{\frac {1}{6}}+{\frac {1}{7}}+{\frac {1}{8}}\right)+\ldots .\end{aligned}}$

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

${\begin{aligned}\sum _{i=1}^{\nu }{\frac {1}{i}}&=1+{\frac {1}{2}}+\left({\frac {1}{4}}+{\frac {1}{4}}\right)+\left({\frac {1}{8}}+{\frac {1}{8}}+{\frac {1}{8}}+{\frac {1}{8}}\right)+\ldots \\&\geq 1+{\frac {1}{2}}+{\frac {1}{2}}+{\frac {1}{2}}+\ldots \\&\to \infty ,\end{aligned}}$

που αποκλίνει καθώς το δεξί μέλος αποτελείται από το άθροισμα απείρων σταθερών όρων.

Για την γενική περίπτωση (με $\alpha _{1},\omega >0$, αρκεί να παρατηρήσουμε ότι για $\nu \geq \max(1,1/(\alpha _{1}\omega ))=:M$, ισχύει ότι

$\alpha _{\nu }={\frac {1}{{\frac {1}{\alpha _{1}}}+(\nu -1)\cdot \omega }}\geq {\frac {1}{2(\nu -1)\cdot \omega }}$.

Επομένως,

$\sum _{i=1}^{\infty }\alpha _{i}\geq \sum _{i=M}^{\infty }\alpha _{i}\geq \sum _{i=M}^{\infty }{\frac {1}{2(\nu -1)\cdot \omega }}={\frac {1}{2\omega }}\sum _{i=M-1}^{\infty }{\frac {1}{\nu }}\to \infty .$

Συνεπώς, καταλήγουμε ότι η σειρά αποκλίνει.

Υπολογισμός

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

#include <iostream>

int main() {
   double a_1 = 4.0;
   double omega = 1.5;
   
   double a_n = a_1;
   for (int n = 1; n <= 5; ++n) {
     std::cout << "a_" << n << " = " << a_n << ", ";
     a_n = 1.0/(omega + a_n); // Υπολογισμός επόμενου όρου.
   }
   return 0;
}
/* Τυπώνει: a_1 = 4, a_2 = 5.5, a_3 = 7, a_4 = 8.5, a_5 = 10, */

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

double harmonic_nth(double a1, double omega, int n) {
   return 1.0 / (a1 + (n - 1) * omega);
}

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

double harmonic_nth_recursive(double a1, double omega, int n) {
   if (n == 1) return a1;
   return omega + harmonic_nth_recursive(a1, omega, n-1);
}

Εφαρμογές

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

Πλήθος μεγίστων προθέματος

Σε μία τυχαία μετάθεση των στοιχείων $\{1,2,\ldots ,\nu \}$, η αναμενόμενη τιμή του πλήθους $M$ των στοιχείων που είναι μεγαλύτερα από όλα τα προηγούμενά τους είναι

$\operatorname {E} [M]=1+{\frac {1}{2}}+{\frac {1}{3}}+\ldots +{\frac {1}{\nu }}$.

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

Πρόβλημα του συλλέκτη κουπονιών

Στο πρόβλημα του συλλέκτη κουπονιών, ένας συλλέκτης μαζεύει κουπόνια (γραμματόσημα ή αυτοκόλλητα ποδοσφαίρου) και υπάρχουν $\nu$ διαθέσιμοι τύποι κουπονιών. Κάθε φορά που αγοράζει έναν φάκελο παίρνει ένα από τα κουπόνια, του οποίου ο τύπος καθορίζεται τυχαία, ο κάθε ένας με πιθανότητα $1/\nu$. Η αναμενόμενη τιμή τιμή του χρόνου $T$ που χρειάζεται μέχρι να μαζέψει όλα τα $\nu$ κουπόνια δίνεται από το άθροισμα των πρώτων όρων μίας αρμονικής προόδου (πολλαπλασιασμένο με $\nu$),

$\operatorname {E} [T]=\nu \cdot \sum _{i=1}^{n}{\frac {1}{i}}$.

Μεγιστοποίηση κρεμάσματος

Τα πρώτα εννιά τραπουλόχαρτα στην λύση που μεγιστοποιεί το κρέμασμα.

Μας δίνονται $N$ πανομοιότυπα τραπουλόχτα και μας ζητείται να ατα τοποθετήσουμε στην άκρη ενός τραπεζιού ώστε να μεγιστοποιηθεί το μήκος εκτός τραπεζιού και τα τραπουλόχαρτα να μην πέσουν. Η μέγιστη απόσταση δίνεται απο το άθροισμα των όρων μία αρμονικής προόδου, δηλαδή είναι ίση με

${\frac {1}{2}}+{\frac {1}{4}}+\ldots +{\frac {1}{2\nu }}=\sum _{i=1}^{\nu }{\frac {1}{2i}}$.

Περαιτέρω ανάγνωση

Ελληνικά άρθρα

• Γκουβιέρος, Χ. (1982). «Πρόοδοι». Ευκλείδης Β΄ (Ελληνική Μαθηματική Εταιρεία) (4). http://niobe.hms.gr/apothema/?s=sa&i=3314. 

Δείτε επίσης

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