חשבון אינפיניטסימלי/מושגים בסיסיים בתורת הקבוצות/אינדוקציה/פתרונות לתרגילים

פתרון תרגיל מספר 1

פתרון סעיף א'

צ"ל: לכל $\ n\geq 3$ טבעי מתקיים: $\ n^{n+1}>\left(n+1\right)^{n}$.
הוכחה: נוכיח באינדוקציה:
שלב א': בסיס האינדוקציה: נבדוק עבור $\ n=3$: $\ 81=3^{4}>4^{3}=64$ - מתקיים.
שלב ב': הנחת האינדוקציה: נניח נכונות הטענה עבור $\ n$, כלומר נניח שמתקיים:

$\ n^{n+1}=n\cdot n^{n}>\left(n+1\right)^{n}$

במילים אחרות, אנו מניחים שמתקיים:

$\ n>\left({\frac {n+1}{n}}\right)^{n}$

שלב ג': צעד האינדוקציה: עלינו להוכיח כי מתקיים:

$\ n+1>\left({\frac {n+2}{n+1}}\right)^{n+1}$

הוכחה: ראשית נבדוק: האם מתקיים:

$\ \left({\frac {n+2}{n+1}}\right)^{n}<\left({\frac {n+1}{n}}\right)^{n}$? 

הנ"ל מתקיים רק אם מתקיים: $\ {\frac {n+2}{n+1}}<{\frac {n+1}{n}}$ (מותר להוציא שורש כי כל האיברים חיוביים),
וזה מתקיים רק אם: $\ n^{2}+2n<n^{2}+2n+1$. מכיוון שהביטוי האחרון מתקיים תמיד (כי הוא שקול לביטוי $\ 0<1$, שנכון תמיד) הרי שקיבלנו שהביטוי המקורי שלנו נכון.

נכפול את שני אגפי אי-השיוויון שהתקבל בביטוי $\ \left({\frac {n+2}{n+1}}\right)$. נקבל:

$\left({\frac {n+2}{n+1}}\right)\left({\frac {n+2}{n+1}}\right)^{n}<\left({\frac {n+2}{n+1}}\right)\left({\frac {n+1}{n}}\right)^{n}\underbrace {<} _{(*)}\left({\frac {n+2}{n+1}}\right)n$

כאשר ב- $(*)$ הצבנו את הנחת האינדוקציה.
כעת נבדוק: האם מתקיים:

$\ \left({\frac {n+2}{n+1}}\right)n<n+1$ ?

הנ"ל מתקיים אמ"מ $\ n^{2}+2n<n^{2}+2n+1$, וכבר ראינו שביטוי זה מתקיים תמיד. לכן, גם אי השיוויון הזה הוכח.
נסכם את כל מה שראינו עד כה:
$\ \left({\frac {n+2}{n+1}}\right)^{n+1}=\left({\frac {n+2}{n+1}}\right)\left({\frac {n+2}{n+1}}\right)^{n}<\left({\frac {n+2}{n+1}}\right)\left({\frac {n+1}{n+2}}\right)^{n}<\left({\frac {n+2}{n+1}}\right)n<n+1$. כלומר: $\ \left({\frac {n+2}{n+1}}\right)^{n+1}<n+1$ ▪

• הערה: הקורא אשר נתקל בפתרון זה לראשונה עלול להיבהל, ולא להבין "מאיפה זה הגיע". קחו לתשומת לבכם את העובדה, כי זהו פתרון "מסודר", כלומר לא מפורט בו תהליך החשיבה של הפותר אלא רק התוצאה הסופית שלו. במציאות, צריך לרוב "לשחק" קצת עם מה שאנחנו רוצים להוכיח עד שנגיע לביטוי שדומה להנחת האינדוקציה, ו"משחק" זה מתווה לנו את דרך ההוכחה.

פתרון סעיף ב'

צ"ל: לכל $\ n\in \mathbb {N}$ מתקיים: $\ {\frac {2^{2n-1}}{\sqrt {n}}}\leq {2n \choose n}\leq {\frac {2^{2n}}{\sqrt {3n+1}}}$
הוכחה: נפתח בהוכחת צד ימין. נוכיח באינדוקציה.
א. בסיס האינדוקציה: נבדוק נכונות הטענה עבור $\ n=1$:

$\ 2={\frac {2}{1}}={\frac {2!}{\left(1!\right)^{2}}}={\frac {\left(2n\right)!}{\left(n!\right)^{2}}}={\frac {\left(2n\right)!}{n!n!}}={2n \choose n}\leq {\frac {2^{2n}}{\sqrt {3n+1}}}={\frac {2^{2}}{\sqrt {4}}}={\frac {4}{2}}=2$

כלומר $\ n=1$ מקיים את הטענה.
ב. הנחת האינדוקציה: נניח נכונות הטענה עבור $\ n$.
ג. צעד האינדוקציה: עלינו להוכיח שמתקיים: $\ {\frac {\left(2n+2\right)!}{\left(n+1\right)!^{2}}}\leq {\frac {2^{2n+2}}{\sqrt {3n+4}}}$

פתרון תרגיל מספר 2

יש להראות שלכל $\ n\in \mathbb {N}$ מתקיים: $\ \sum _{k=0}^{n}{n \choose k}a^{k}b^{n-k}=(a+b)^{n}$.

נוכיח באינדוקציה.

בסיס האינדוקציה הוא עבור $\ n=1$ והוא מיידי: $\ \sum _{k=0}^{1}{1 \choose k}a^{k}b^{n-k}=a+b=(a+b)^{1}$

נניח כי עבור $\ n$ מתקיים $\ \sum _{k=0}^{n}{n \choose k}a^{k}b^{n-k}=(a+b)^{n}$.

צריך להראות כי עבור $\ n+1$ מתקיים $\ \sum _{k=0}^{n+1}{n+1 \choose k}a^{k}b^{n+1-k}=(a+b)^{n+1}$.

הוכחה: אנו יודעים מהנחת האינדוקציה כי $\ \sum _{k=0}^{n}{n \choose k}a^{k}b^{n-k}=(a+b)^{n}$. נכפול את שני האגפים ב-$\ (a+b)$. באגף ימין נקבל $\ (a+b)^{n+1}$ ולכן נשאר להוכיח שאגף ימין שווה ל-$\ \sum _{k=0}^{n+1}{n+1 \choose k}a^{k}b^{n+1-k}$.

נפתח את אגף שמאל:

$\ (\sum _{k=0}^{n}{n \choose k}a^{k}b^{n-k})(a+b)=\sum _{k=0}^{n}{n \choose k}a^{k+1}b^{n-k}+\sum _{k=0}^{n}{n \choose k}a^{k}b^{n-k+1}=$

$\ =a^{n+1}+\sum _{k=0}^{n-1}{n \choose k}a^{k+1}b^{n-k}+\sum _{k=1}^{n}{n \choose k}a^{k}b^{n-k+1}+b^{n+1}=$

$\ =a^{n+1}+\sum _{k=0}^{n-1}{n \choose k}a^{k+1}b^{n-k}+\sum _{k=0}^{n-1}{n \choose k+1}a^{k+1}b^{n-k}+b^{n+1}=$

$\ =a^{n+1}+\sum _{k=0}^{n-1}({n \choose k}+{n \choose k+1})a^{k+1}b^{n-k}+b^{n+1}=$

$\ =a^{n+1}+\sum _{k=0}^{n-1}({n+1 \choose k+1})a^{k+1}b^{n-k}+b^{n+1}=$

$\ =a^{n+1}+\sum _{k=1}^{n}{n+1 \choose k}a^{k}b^{n+1-k}+b^{n+1}=$

$\ =\sum _{k=0}^{n+1}{n+1 \choose k}a^{k}b^{n+1-k}$

השתמשנו בזהות הקומבינטורית $\ {n \choose k}+{n \choose k+1}={n+1 \choose k+1}$.

==פתרון תרגיל מספר 3==

פתרון סעיף א'

א. הוכיחו שלכל $\ n\in \mathbb {N}$ מתקיים: $\ \sum _{k=1}^{n}{\frac {1}{k\left(k+1\right)}}={\frac {n}{n+1}}$ נתבונן ב: $\ {\frac {1}{k\left(k+1\right)}}$ נראה שהוא בעצם:$\ {\frac {1\left(k\right)}{-}}{\frac {1}{1\left(k+1\right)}}$ עכשיו נתבונן בסכום לאחר הצבה: $\ {\frac {1}{1\left(1\right)}}-{\frac {1}{1\left(2\right)}}+{\frac {1}{1\left(2\right)}}-{\frac {1}{1\left(3\right)}}$…$\ {\frac {1}{1\left(n\right)}}-{\frac {1}{1\left(n+1\right)}}$ נבחין שזהו טור טלסקופי. ונצמצם. ${\frac {1}{1\left(1\right)}}-{\frac {1}{1\left(n+1\right)}}$ שזה בדיוק: $\ {\frac {n}{n+1}}$

פתרון סעיף ב'

ב. מצאו ביטוי המפשט את $\ \sum _{k=2}{n}\left(1-{\frac {1}{k^{2}}}\right)$.