επαγωγική αποδεικτική μέθοδο, «Μαθηματική Επαγωγή»

Αποδείξτε με τη μέθοδο της επαγωγής ότι σε σύνολο S που αποτελείται από n≥1 πραγματικούς αριθμούς   για τους οποίους ισχύει  και   για  , το άθροισμα των στοιχείων κάθε υποσυνόλου του συνόλου S είναι μοναδικό, δηλαδή διαφορετικό από το άθροισμα των στοιχείων κάθε άλλου υποσυνόλου. Το άθροισμα των στοιχείων του κενού συνόλου θεωρείται ίσο με 0. (Υπόδειξη: Προσέξτε ότι τα υποσύνολα του συνόλου S μπορούν να χωριστούν σε δύο ομάδες, στα υποσύνολα που περιέχουν το μεγαλύτερο στοιχείο και σε εκείνα που δεν το περιέχουν. Επιπλέον υπάρχει μια αντιστοιχία «1-1» ανάμεσα στα υποσύνολα των δύο ομάδων). 

ΑΠΑΝΤΗΣΗ

-----------------------------------------

Θα αποδείξουμε με την μέθοδο τα της επαγωγής 

Βάση επαγωγής

Για n=1 Έχουμε S={1} για το οποίο 0<1 .="" nbsp="" p="" s="">

Υπόθεση επαγωγής

Έστω ότι η προς απόδειξη σχέση ισχύει για n=k 

Τότε θα έχουμε ένα σύνολο με Sk με k στοιχειά δηλαδή

Sk={a1,a2,a3,… ak) με 0

Οπού όλα τα υποσύνολα του Sk έχουν διαφορετικό  άθροισμα στοιχειών.

Επαγωγικό βήμα 

για n=k +1

Έστω  ένα σύνολο με Sk+1  με k+1 στοιχειά δηλαδή

Sk+1={a1,a2,a3,… ak,ak+1) με 0

Θα δείξουμε ότι όλα τα υποσύνολα του Sk+1 έχουν διαφορετικό άθροισμα στοιχειών.

Ξεκινώντας

 Θεωρούμε δυο σύνολα Χ και W που είναι γνήσια υποσύνολα του Sk+1  θα δείξουμε ότι τα δυο υποσύνολα έχουν διαφορετικό άθροισμα στοιχειών δηλαδή

X,W   Sk+1

Διακρίνουμε τις Παρακάτω περιπτώσεις

Τα X, W υποσύνολα να μην περιέχουν τα στοιχείο  aκ+1  δηλαδή τα Σύνολα Χ και W θα περιέχουν τα στοιχειά  {a1,a2,a3,… ak}  Επομένως από την επαγωγική υπόθεση έχουμε ότι το άθροισμα είναι διαφορετικό αρά σε αυτή την περίπτωση ισχύει.

Η δεύτερη περίπτωση είναι να ανήκει aκ+1    στο υποσύνολο Χ και στο Υποσύνολο W δηλαδή aκ+1  ∈ X και aκ+1  ∈ W.   

Αρχικά θεωρούμε τα Σύνολα Χ’ και W’ (που είναι γνήσια υποσύνολα του Sk+1) με το aκ+1 να μην ανήκει  στα δυο σύνολα δηλαδή τα Σύνολα Και  W’ θα περιέχουν τα στοιχεία  {a1,a2,a3,… ak) που όπως είδαμε και παραπάνω από την επαγωγική  υπόθεση το άθροισμα των στοιχείων κάθε υποσύνολου είναι μοναδικό. Τώρα στα δυο σύνολα εάν προσθέσω και στα δυο χωριστά το ίδιο στοιχείο  aκ+1  το άθροισμα θα παραμείνει διαφορετικό δηλαδή

X’=X-{ aκ+1}  και  W’=W-{ aκ+1} με X’W’   Sk  Από επαγωγική υπόθεση έχουν διαφορετικό άθροισμα

Άρα και τα Χ και W έχουν διαφορετικό άθροισμα

Τέλος έχουμε την περίπτωση που το aκ+1   να  υπάρχει σε ένα από τα δυο υποσύνολα είτε στο Χ είτε στο W δηλαδή aκ+1  ∈ X και aκ+1  ∉ W ή   aκ+1 ∉  X και aκ+1  ∈ W

Ξεκινάμε με aκ+1  ∈ X και aκ+1  ∉ W

Αρχικά από την ανοσιότητα ak

Β≤α1+α2+…ακ   θα δείξουμε  ότι είναι μικρότερο η ισο με ακ+1 ≤ άθροισμα Α

Έχουμε    W ≤a1+a2+a3, +… + ak   

                                                             και  aκ+1 άθροισμα Α

Έχουμε 〖2α〗_ι<〖2α〗_ι+1=α_ι<(〖2α〗_ι+1)/2

Έχουμε ότι   α_1≤α2/2≤α3/4≤α4/8≤⋯

Είναι δηλαδή 

Το άθροισμα του Β είναι σχεδόν όσο τα υπόλοιπα τις ακολουθίας

α_1≤α_2/2≤α_3/2^2 ≤α_4/2^3 ≤⋯.≤α_(κ+1)/2^κ 

Και ισχύει 

am ≤   α_(κ+1)/2^(κ+1-m) 

Γενικά ισχύει ότι

a1+a2+…+ak ≤ α_(κ+1)/2^κ +α_(κ+1)/2^(κ-2) ..+α_(κ+1)/2^1 

                     =ακ+1(1/2+1/2^1 +…+1/2^(κ-1) +1/2^κ )

                    = 1/2 ακ+1(1+1/2+⋯+1/2^(κ-1) )

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