תרגול 4 תשעז - היסטוריית גרסאות

Relweiz: /* הכללה פשוטה שנייה */

2019-12-08T12:12:52Z

הכללה פשוטה שנייה

→ הגרסה הקודמת		גרסה מ־12:12, 8 בדצמבר 2019
שורה 92:		שורה 92:
	בהנחה שמתקיים עבור כל מי ש'''קטן שווה''' <math>n</math> ולהוכיח עבור <math>n+1</math>.		בהנחה שמתקיים עבור כל מי ש'''קטן שווה''' <math>n</math> ולהוכיח עבור <math>n+1</math>.

	~~'''דוגמה:'''~~		====תרגיל (בד"כ נעשה בהרצאה)====
	כל מספר טבעי <math>1<n </math> ניתן להציגו כמכפלה של מספרים ראשוניים.		כל מספר טבעי <math>1<n </math> ניתן להציגו כמכפלה של מספרים ראשוניים.

שורה 108:		שורה 108:

	אזי <math>n+1=ab=\prod_{k=1}^l p_k\cdot \prod_{i=1}^r q_i</math> וסיימנו.		אזי <math>n+1=ab=\prod_{k=1}^l p_k\cdot \prod_{i=1}^r q_i</math> וסיימנו.

			====תרגיל====
			שאלת השוקולוד.

	=תרגילים יותר מעניינים=		=תרגילים יותר מעניינים=

Mathzeta2: /* הכללה פשוטה שנייה */

2017-11-11T16:43:00Z

הכללה פשוטה שנייה

→ הגרסה הקודמת		גרסה מ־16:43, 11 בנובמבר 2017
שורה 105:		שורה 105:
	אחרת <math>n+1</math> מתפרק למכפלה <math>n+1=ab</math> כאשר <math>1<a,b<n+1</math>		אחרת <math>n+1</math> מתפרק למכפלה <math>n+1=ab</math> כאשר <math>1<a,b<n+1</math>
	לפי הנחת האינדוקציה <math>a,b</math> מתפרקים למכפלה של מספרים ראשוניים		לפי הנחת האינדוקציה <math>a,b</math> מתפרקים למכפלה של מספרים ראשוניים
	<math>a=\~~Pi_~~{k=1}^l p_k,b=\~~Pi_~~{i=1}^r q_i</math> כאשר <math>p_k,q_i</math> ראשוניים.		<math>a=\prod_{k=1}^l p_k,b=\prod_{i=1}^r q_i</math> כאשר <math>p_k,q_i</math> ראשוניים.

	אזי <math>n+1=ab=\~~Pi_~~{k=1}^l p_k\cdot \~~Pi_~~{i=1}^r q_i</math> וסיימנו.		אזי <math>n+1=ab=\prod_{k=1}^l p_k\cdot \prod_{i=1}^r q_i</math> וסיימנו.

	=תרגילים יותר מעניינים=		=תרגילים יותר מעניינים=

Mathzeta2: /* הכללה פשוטה ראשונה */

2017-11-11T02:45:13Z

הכללה פשוטה ראשונה

→ הגרסה הקודמת		גרסה מ־02:45, 11 בנובמבר 2017
שורה 67:		שורה 67:

	'''דוגמה:'''		'''דוגמה:'''
	הוכח כי לכל <math>x>0</math> מתקיים <math>(1+x)^n > 1+nx</math> לכל <math>n\geq 2</math>		הוכח כי לכל <math>x>0</math> מתקיים <math>(1+x)^n > 1+nx</math> לכל <math>n\geq 2</math>.

	פתרון:		פתרון:

	עבור <math>n=2</math> נקבל <math>(1+x)^2 = 1+2x+x^2>1+2x</math> כי <math>x>0</math>		עבור <math>n=2</math> נקבל <math>(1+x)^2 = 1+2x+x^2>1+2x</math> כי <math>x>0</math> .

	כעת נניח כי הטענה נכונה עבור <math>n</math> כלשהו, כלומר מתקיים <math>(1+x)^n > 1+nx</math>		כעת נניח כי הטענה נכונה עבור <math>n</math> כלשהו, כלומר מתקיים <math>(1+x)^n > 1+nx</math>.

	נוכיח עבור <math>n+1</math> מהנחת האינדוקציה נקבל כי		נוכיח עבור <math>n+1</math> מהנחת האינדוקציה נקבל כי
	<math> (1+x)^{n+1}=(1+x)^n\cdot (1+x)>(1+nx) (1+x)= 1+nx +x+nx^2 > 1+x+nx =1+ (n+1)x </math>		<math>(1+x)^{n+1}=(1+x)^n\cdot (1+x)>(1+nx) (1+x)</math>
			<math>=1+nx +x+nx^2 > 1+x+nx =1+ (n+1)x</math>

	וסיימנו.		וסיימנו.

Mathzeta2: /* אינדוקציה מתמטית: רעיון בסיסי */

2017-11-11T02:37:35Z

אינדוקציה מתמטית: רעיון בסיסי

→ הגרסה הקודמת		גרסה מ־02:37, 11 בנובמבר 2017
שורה 10:		שורה 10:
	* (צעד האינדוקציה) '''אם''' הטענה נכונה עבור מספר טבעי מסוים, אז היא נכונה גם עבור המספר הבא אחריו. כלומר <math>P(n)\rightarrow P(n+1)</math>.		* (צעד האינדוקציה) '''אם''' הטענה נכונה עבור מספר טבעי מסוים, אז היא נכונה גם עבור המספר הבא אחריו. כלומר <math>P(n)\rightarrow P(n+1)</math>.

	למה זה מספיק? בוא נחשוב. הוכחנו באופן ישיר כי הטענה נכונה עבור <math>n=1</math> כלומר <math>P(1)</math> מתקיים. לכן לפי הטענה השניה, אם הטענה נכונה עבור <math>n=1</math> (שזה אכן כך) אז הטענה נכונה גם עבור <math>n=2</math>כלומר <math>P(2)</math>. אה! אז עכשיו זה נכון עבור <math>n=2</math> אז לפי אותה טענה זה נכון גם עבור <math>n=3</math>! ומה עכשיו? אם זה נכון עבור <math>n=3</math> זה נכון עבור <math>n=4</math> . וכן ~~על זה~~ הדרך. אפשר להשתכנע שבסופו של דבר <math>P(n)</math> נכון '''לכל''' <math>n</math>.		למה זה מספיק? בוא נחשוב. הוכחנו באופן ישיר כי הטענה נכונה עבור <math>n=1</math> כלומר <math>P(1)</math> מתקיים. לכן לפי הטענה השניה, אם הטענה נכונה עבור <math>n=1</math> (שזה אכן כך) אז הטענה נכונה גם עבור <math>n=2</math>. כלומר <math>P(2)</math>. אה! אז עכשיו זה נכון עבור <math>n=2</math>, אז לפי אותה טענה זה נכון גם עבור <math>n=3</math>! ומה עכשיו? אם זה נכון עבור <math>n=3</math>, זה נכון עבור <math>n=4</math>. וכן הלאה באותה הדרך. אפשר להשתכנע שבסופו של דבר <math>P(n)</math> נכון '''לכל''' <math>n</math>.

	'''דוגמה:'''		'''דוגמה:'''

Mathzeta2: /* רעיון בסיסי - אינדוקציה על הטבעיים */

2017-11-11T02:34:18Z

רעיון בסיסי - אינדוקציה על הטבעיים

הצגת שינויים

464497330: /* הכללה פשוטה 1 */

2017-11-06T21:00:19Z

הכללה פשוטה 1

→ הגרסה הקודמת		גרסה מ־21:00, 6 בנובמבר 2017
שורה 59:		שורה 59:
	הכללה ישירה מתבצעת כך (החלפה רק של הטענה הראשונה): אם נוכיח עבור טענה <math>P(n)</math> ש:		הכללה ישירה מתבצעת כך (החלפה רק של הטענה הראשונה): אם נוכיח עבור טענה <math>P(n)</math> ש:
	* הטענה מתקיימת עבור <math>n=k</math> מסוים כלומר <math>P(k)</math> מתקיים		* הטענה מתקיימת עבור <math>n=k</math> מסוים כלומר <math>P(k)</math> מתקיים
	* '''אם''' הטענה נכונה עבור מספר טבעי מסוים אזי היא נכונה גם עבור המספר הבא אחריו. כלומר <math>P(n)\~~Rightarrow~~ P(n+1)</math>.		* '''אם''' הטענה נכונה עבור מספר טבעי מסוים אזי היא נכונה גם עבור המספר הבא אחריו. כלומר <math>P(n)\rightarrow P(n+1)</math>.

	אז באופן דומה הטענה נכונה <math>P(n)</math> נכונה עבור <math>n\geq k</math>		אז באופן דומה הטענה נכונה <math>P(n)</math> נכונה עבור <math>n\geq k</math>

464497330: /* רעיון בסיסי - אינדוקציה על הטבעיים */

2017-11-06T20:59:39Z

רעיון בסיסי - אינדוקציה על הטבעיים

→ הגרסה הקודמת		גרסה מ־20:59, 6 בנובמבר 2017
שורה 6:		שורה 6:
	(למשל <math>(1+2+\cdots +n)^2 =1^3 +2^3 + \cdots +n^3</math>) מספיק להוכיח את הבאים:		(למשל <math>(1+2+\cdots +n)^2 =1^3 +2^3 + \cdots +n^3</math>) מספיק להוכיח את הבאים:
	* (בסיס האינדוקציה) הטענה מתקיימת עבור <math>n=1</math> כלומר <math>P(1)</math> מתקיים		* (בסיס האינדוקציה) הטענה מתקיימת עבור <math>n=1</math> כלומר <math>P(1)</math> מתקיים
	* (צעד האינדוקציה)'''אם''' הטענה נכונה עבור מספר טבעי מסוים אזי היא נכונה גם עבור המספר הבא אחריו. כלומר <math>P(n)\~~Rightarrow~~ P(n+1)</math>.		* (צעד האינדוקציה)'''אם''' הטענה נכונה עבור מספר טבעי מסוים אזי היא נכונה גם עבור המספר הבא אחריו. כלומר <math>P(n)\rightarrow P(n+1)</math>.

	למה זה מספיק?		למה זה מספיק?

Mathzeta2 ב־17:36, 24 באוקטובר 2017

2017-10-24T17:36:59Z

→ הגרסה הקודמת		גרסה מ־17:36, 24 באוקטובר 2017
שורה 1:		שורה 1:
			חזרה ל[[83-116, בדידה 1 להנדסה, מערכי תרגול\|דף מערכי התרגול]].

	=רעיון בסיסי - אינדוקציה על הטבעיים=		=רעיון בסיסי - אינדוקציה על הטבעיים=

אריאל: יצירת דף עם התוכן "=רעיון בסיסי - אינדוקציה על הטבעיים= בשביל להוכיח שטענה מסוימת $P(n)$ נכונה עבור כל מ..."

2016-11-29T13:21:50Z

יצירת דף עם התוכן "=רעיון בסיסי - אינדוקציה על הטבעיים= בשביל להוכיח שטענה מסוימת <math>P(n)</math> נכונה עבור כל מ..."

דף חדש

=רעיון בסיסי - אינדוקציה על הטבעיים=

בשביל להוכיח שטענה מסוימת <math>P(n)</math> נכונה עבור כל מספר טבעי
(למשל <math>(1+2+\cdots +n)^2 =1^3 +2^3 + \cdots +n^3</math>) מספיק להוכיח את הבאים:
* (בסיס האינדוקציה) הטענה מתקיימת עבור <math>n=1</math> כלומר <math>P(1)</math> מתקיים
* (צעד האינדוקציה)'''אם''' הטענה נכונה עבור מספר טבעי מסוים אזי היא נכונה גם עבור המספר הבא אחריו. כלומר <math>P(n)\Rightarrow P(n+1)</math>.

למה זה מספיק?
בוא נחשוב.. הוכחנו באופן ישיר כי הטענה נכונה עבור <math>n=1</math> כלומר <math>P(1)</math> מתקיים. לכן לפי הטענה השניה, אם הטענה נכונה עבור <math>n=1</math> (שזה אכן כך) אז הטענה נכונה גם עבור <math>n=2</math>כלומר <math>P(2)</math>. אה! אז עכשיו זה נכון עבור <math>n=2</math> אז לפי אותה טענה זה נכון גם עבור <math>n=3</math>! ומה עכשיו? אם זה נכון עבור <math>n=3</math> זה נכון עבור <math>n=4</math> . וכן על זה הדרך. אפשר להשתכנע שבסופו של דבר <math>P(n)</math> נכון '''לכל''' <math>n</math>

דוגמא:
נוכיח באינדוקציה כי הטענה <math>(1+2+\cdots +n)^2 =1^3 +2^3 + \cdots +n^3</math>
נכונה לכל <math>n\in \mathbb{N} </math> טבעי

הוכחה:

עבור <math>n=1</math> אכן מתקיים כי <math>1^2=1^3</math>

כעת נראה שאם הטענה נכונה עבור <math>n</math> כלשהוא, כלומר אם מתקיים
<math>(1+2+\cdots +n)^2 =1^3 +2^3 + \cdots +n^3</math> אזי הטענה נכונה עבור <math>n+1</math>, כלומר
<math>(1+2+\cdots +n+(n+1))^2 =1^3 +2^3 + \cdots +n^3 + (n+1)^3</math>. כלומר נוכיח ש: <math>P(n) \to P(n+1)</math>

נוכיח:

<math>(1+2+\cdots +n+(n+1))^2=(1+2+\cdots +n)^2+2\cdot(1+2+\cdots +n)(n+1)+(n+1)^2 </math>

לפי הנחת האינדוקציה אפשר להמשיך הלאה

<math>=1^3 +2^3 + \cdots +n^3 +2\cdot (1+2+\cdots +n)(n+1)+(n+1)^2 </math>
<math>=1^3 +2^3 + \cdots +n^3 +2 \cdot \frac{n(n+1)}{2}(n+1)+(n+1)^2 </math>
<math>=1^3 +2^3 + \cdots +n^3 +n(n+1)^2+(n+1)^2</math>
<math>=1^3 +2^3 + \cdots +n^3 +(1+n)(n+1)^2=1^3 +2^3 + \cdots +n^3+(n+1)^3</math>

וסיימנו

דוגמא נוספת:

הוכח כי לכל מספר טבעי <math>n</math> מתקיים כי <math>2+4+6+\cdots +2n=n(n+1)</math>

פתרון:

עבור <math>n=1</math> אכן מתקיים <math>2=1\cdot(1+1)</math>

כעת נניח שהטענה נכונה עבור <math>n</math> ונוכיח את הטענה עבור <math>n+1</math>

<math>2+4+\cdots 2n+2(n+1)=\sum_{k=1}^{n+1}2\cdot k=\sum_{k=1}^{n}2\cdot k + 2(n+1) = </math>

לפי הנחת האינדוקציה ניתן להמשיך

<math>=n(n+1)+2(n+1)=(n+1)(n+2)</math>

שזה הטענה עבור <math>n+1</math> וסיימנו.

==הכללות==
===הכללה פשוטה 1===
הכללה ישירה מתבצעת כך (החלפה רק של הטענה הראשונה): אם נוכיח עבור טענה <math>P(n)</math> ש:
* הטענה מתקיימת עבור <math>n=k</math> מסוים כלומר <math>P(k)</math> מתקיים
* '''אם''' הטענה נכונה עבור מספר טבעי מסוים אזי היא נכונה גם עבור המספר הבא אחריו. כלומר <math>P(n)\Rightarrow P(n+1)</math>.

אז באופן דומה הטענה נכונה <math>P(n)</math> נכונה עבור <math>n\geq k</math>

כלומר - במקום להוכיח עבור <math>n=1</math> ואז הטענה מתקיים החל מ-1 ניתן להוכיח עבור <math>n=k</math> ואז הטענה מתקיים החל מ-k

דוגמא:

הוכח כי לכל <math>x>0</math> מתקיים <math>(1+x)^n > 1+nx</math> לכל <math>n\geq 2</math>

פתרון:

עבור <math>n=2</math> נקבל <math>(1+x)^2 = 1+2x+x^2>1+2x</math> כי <math>x>0</math>

כעת נניח כי הטענה נכונה עבור <math>n</math> כלשהוא, כלומר מתקיים <math>(1+x)^n > 1+nx</math>

נוכיח עבור <math>n+1</math> מהנחת האינדוקציה נקבל כי
<math> (1+x)^{n+1}=(1+x)^n\cdot (1+x)>(1+nx) (1+x)= 1+nx +x+nx^2 > 1+x+nx =1+ (n+1)x </math>

וסיימנו

===הכללה פשוטה 2 ===
אם נוכיח עבור טענה <math>P(n)</math> ש:
* הטענה מתקיימת עבור <math>n=1</math> מסוים כלומר <math>P(1)</math> מתקיים
* '''אם''' הטענה נכונה עבור כל המספרים עד מספר טבעי מסוים <math>n</math> (כלומר מתקיים <math>P(m)</math> עבור <math>m\leq n</math>) אזי היא נכונה גם עבור המספר הבא אחריו (כלומר <math>P(n+1)</math> מתקיים).

אז באופן דומה הטענה נכונה <math>P(n)</math> נכונה עבור <math>n\geq 1</math>

כלומר - אפשר להחליף את ההנחה שמתקיים עבור <math>n</math> ולהוכיח עבור <math>n+1</math>
בהנחה שמתקיים עבור כל מי ש'''קטן שווה''' <math>n</math> ולהוכיח עבור <math>n+1</math>

דוגמא:
כל מספר טבעי <math>1<n </math> ניתן להציגו כמכפלה של מספרים ראשוניים

הוכחה:

עבור <math>n=2</math> זה נכון כי 2 ראשוני ואז הוא הפירוק של עצמו.

כעת נניח שהטענה נכונה לכל <math>1<k\leq n</math> ונוכיח עבור <math>n+1</math>

אם <math>n+1</math> ראשוני - סיימנו כי אז הוא הפירוק של עצמו.

אחרת <math>n+1</math> מתפרק למכפלה <math>n+1=ab</math> כאשר <math>1<a,b<n+1</math>
לפי הנחת האינדוקציה <math>a,b</math> מתפרקים למכפלה של מספרים ראשוניים
<math>a=\Pi_{k=1}^l p_k,b=\Pi_{i=1}^r q_i</math> כאשר <math>p_k,q_i</math> ראשוניים

ואז <math>n+1=ab=\Pi_{k=1}^l p_k\cdot \Pi_{i=1}^r q_i</math>

וסיימנו.

== תרגילים יותר מעניינים ==
===תרגיל ===
יהא <math>A</math> פסוק. נגדיר בעזרת אינדוקציה פסוקים:
<math>P_0 = A, P_n=(P_{n-1})\to A</math>
הוכיחו כי <math>P_{n}</math>
טואוטולוגיה כאשר <math>n</math> אי-זוגי.

פתרון: נוכיח באינדוקציה כי לכל <math>n</math> אי-זוגי, הפסוק <math>P_{n}</math>
הוא טואוטולוגיה.בדיקה: עבור <math>n=1</math>, הפסוק הוא <math>A\to A</math>. הוא אכן טואוטולוגיה.

צעד: כעת, נניח את נכונות הטענה עבור <math>n</math> אי-זוגי, ונוכיח עבור האי-זוגי הבא בתור, כלומר <math>n+2</math>.

מתקיים:<math>P_{n+2}=P_{n+1}\to A=(P_{n}\to A)\to A</math> נראה כי זו אכן טואוטולוגיה. ראשית, לפי ההנחה, <math>P_{n}\equiv T</math>
לכל ערך של <math>A</math>.

• אם <math>A=F</math>, נקבל <math>(T\to F)\to F\equiv F\to F</math>- אכן אמת.

• אם <math>A=T</math>, נקבל <math> (T\to T)\to T\equiv T\to T</math> - אכן אמת.

וסיימנו באינדוקציה.

===תרגיל:===

יהיו <math>A_1,A_2\dots A_{m+1} \in \mathbb{F}^{n\times n}</math> מטריצות ריבועיות אזי האיבר הכללי של המכפלה של כולם ניתן ע"י הנוסחא
<math>(A_1A_2\cdots A_{m+1})_{i,j}=\underset{1\leq i_1,i_2,\dots i_m \leq n}{\sum}(A_1)_{i,i_1}(A_2)_{i_1,i_2}\dots (A_{m+1})_{i_m,j}</math>

הוכחה (באינדוקציה על מספר המטריצות):

עבור <math>m=1</math> זה ההגדרה של כפל בין 2 מטריצות

כעת, נניח שהטענה נכונה עבור <math>m</math> כל שהוא. נוכיח נכונות עבור <math>m+1</math>

<math>(A_1A_2\cdots A_{m+1}A_{m+2})_{i,j}=\sum_{i_{m+1}=1}^n (A_1A_2\cdots A_{m+1})_{i,i_{m+1}}(A_{m+2})_{i_{m+1},j}</math>

לפי הנחת האינדוקציה נמשיך:

<math>=\sum_{i_{m+1}=1}^n \underset{1\leq i_1,i_2,\dots i_m \leq n}{\sum}(A_1)_{i,i_1}(A_2)_{i_1,i_2}\dots (A_{m+1})_{i_m,i_{m+1}}(A_{m+2})_{i_{m+1},j} = </math>

<math> = \underset{1\leq i_1,i_2,\dots i_m, i_{m+1} \leq n}{\sum}(A_1)_{i,i_1}(A_2)_{i_1,i_2}\dots (A_{m+1})_{i_m,i_{m+1}}(A_{m+2})_{i_{m+1},j}</math>

וסיימנו.

==אזהרה==
אינדוקציה היא כלי חזק אך יש לשים לב כי משתמשים בו נכונה.

דוגמא מפורסמת להוכחת שגויה באינדוקציה היא הדוגמא הבא:

טענה: כל קבוצה של סוסים לא ריקה מכילה סוסים מצבע יחיד.

"הוכחה": נוכיח בעזרת אינדוקציה על מספר האיברים בקבוצת הסוסים.

עבור <math>n=1</math> אכן מתקיים כי קבוצה עם סוס אחד מכילה רק סוסים מצבע יחיד

כעת נניח כל קבוצה עם <math>n</math> סוסים מכילה סוסים רק מצבע יחיד ונוכיח את הטענה לקבוצת סוסים מגודל <math>n+1</math>

תהא <math>H=\{h_1,h_2,\dots h_n,h_{n+1}\}</math> קבוצה עם <math>n+1</math> סוסים אזי לפי הנחת האינדוקציה
<math>H_1 =\{h_1,h_2,\dots h_n\}</math> ו <math>H_2=\{h_2,\dots h_n,h_{n+1}\}</math> הן קבוצות שמכילות סוסים מצבע יחיד (כי אלו קבוצות סוסים מגודל <math>n</math>)
ולכן כל הסוסים ב <math>H</math> ג"כ בעלי צבע יחיד (כי יש חפיפה בין <math>H_1</math> ובין <math>H_2</math>.

חישבו איפה השגיאה (רמז: במעבר מ <math>n=1</math> ל <math>n=2</math>)