מתמטיקה תיכונית/פתרונות לספרים/מתמטיקה (5 יחידות לימוד) חלק ו' שאלון 035006/עמוד 110 סעיף 28

$n!\leq 1*2*4*8*\cdots *2^{n-1}$

הוכחה א'

בדיקה נכונות הטענה עבור $\ n=1$

${\begin{aligned}&1!\leq 2^{0}\\&1\leq 1\\\end{aligned}}$

נניח כי הטענה נכונה עבור $\ n=k$ טבעי

$k!\leq 1*2*4*8*\cdots *2^{k-1}$

נוכיח כי הטענה נכונה עבור n=k+1

${\begin{aligned}&(k+1)!\leq \underbrace {1*2*4*8*\cdots *2^{k}} _{=k!}*2^{k}\\&\downarrow \\&k!\leq 1*2*4*8*\cdots *2^{k-1}\\&\downarrow \\&k!(k+1)\leq k!*2^{k}\\&k+1\leq 2^{k}\end{aligned}}$

הערות : ליד החצים יש לרשום את הערות הצדדיות על פי הסדר הבא :

1. על פי ההנחה.
2. מספיק להוכיח.

הוכחה במילים

ההנחה נכונה עבור $\ n=1$, לפי הנחת האינדוקציה (הוכחנו בבדיקה).ההנחה נכונה עבור $\ n=2\cdots$ כיוון שלכל k טבעי מתקיים שששתים בחזקת k גדול או שווה ל-k.הוכחה לחוק :

${\begin{aligned}&2^{n}\geq n\\&\downarrow \\&n=k+1\\&\downarrow \\&2^{k+1}\geq k+1\\&2^{k}*2\geq k+1\\\end{aligned}}$

הביטוי $n!\leq 1*2*4*8*\cdots *2^{n-1}$ נכון עבור כל $\ n$ טבעי, על פי שלושת שלבי האינדוקציה.