88-195 בדידה לתיכוניסטים תשעא/מערך שיעור/שיעור 1.5 - היסטוריית גרסאות

אחיה בר-און: /* תרגיל */

2022-07-06T18:47:27Z

תרגיל

→ הגרסה הקודמת		גרסה מ־18:47, 6 ביולי 2022
שורה 188:		שורה 188:
	לכן, הטענה נכונה גם עבור <math>n+1</math> וסיימנו		לכן, הטענה נכונה גם עבור <math>n+1</math> וסיימנו

			=== תרגיל ===
			יהא <math>a</math> מספר ממשי המקיים כי <math>a+\frac{1}{a}</math> מספר שלם. הוכיחו כי לכל <math>n</math> טבעי מתקיים כי <math>a^n+\frac{1}{a^n}</math> מספר שלם.
	=== תרגיל ===		=== תרגיל ===
	לכל <math>n</math> טבעי מתקיים: כל טבלה ריבועית בגודל <math>2^{n}\times2^{n}</math> שהוצאנו ממנה משבצת, ניתן לכסות ב "י" (3 משבצות בצורת האות יוד)		לכל <math>n</math> טבעי מתקיים: כל טבלה ריבועית בגודל <math>2^{n}\times2^{n}</math> שהוצאנו ממנה משבצת, ניתן לכסות ב "י" (3 משבצות בצורת האות יוד)
שורה 198:		שורה 200:

	מסקנה: לכל <math>n</math> טבעי מתקיים ש 3 מחלק את <math>\left(2^{n}\right)^{2}-1</math>.		מסקנה: לכל <math>n</math> טבעי מתקיים ש 3 מחלק את <math>\left(2^{n}\right)^{2}-1</math>.

	=== תרגיל ===		=== תרגיל ===
	תהא טבלת שוקולד עם <math>m</math> שורות ו <math>n</math> עמודות. חיתוך של טבלת שוקולד הוא שבירת הטבלה לשתי טבלאות קטנות לאורך או לרוחב הטבלה המקורית. הוכיחו כי בהינתן טבלה עם <math>N</math> קוביות שוקולד, צריך בדיוק <math>N-1</math> חיתוכים על מנת להפריד כל קוביה בנפרד (כלומר לקבל <math>N</math> טבלאות שכל אחת מגודל 1 על 1).		תהא טבלת שוקולד עם <math>m</math> שורות ו <math>n</math> עמודות. חיתוך של טבלת שוקולד הוא שבירת הטבלה לשתי טבלאות קטנות לאורך או לרוחב הטבלה המקורית. הוכיחו כי בהינתן טבלה עם <math>N</math> קוביות שוקולד, צריך בדיוק <math>N-1</math> חיתוכים על מנת להפריד כל קוביה בנפרד (כלומר לקבל <math>N</math> טבלאות שכל אחת מגודל 1 על 1).

אחיה בר-און: /* תרגיל: */

2021-07-05T06:20:41Z

תרגיל:

→ הגרסה הקודמת		גרסה מ־06:20, 5 ביולי 2021
שורה 198:		שורה 198:

	מסקנה: לכל <math>n</math> טבעי מתקיים ש 3 מחלק את <math>\left(2^{n}\right)^{2}-1</math>.		מסקנה: לכל <math>n</math> טבעי מתקיים ש 3 מחלק את <math>\left(2^{n}\right)^{2}-1</math>.
	===תרגיל:===		=== תרגיל ===
			תהא טבלת שוקולד עם <math>m</math> שורות ו <math>n</math> עמודות. חיתוך של טבלת שוקולד הוא שבירת הטבלה לשתי טבלאות קטנות לאורך או לרוחב הטבלה המקורית. הוכיחו כי בהינתן טבלה עם <math>N</math> קוביות שוקולד, צריך בדיוק <math>N-1</math> חיתוכים על מנת להפריד כל קוביה בנפרד (כלומר לקבל <math>N</math> טבלאות שכל אחת מגודל 1 על 1).

			הוכחה: באינדוקציה שלמה. אם הטבלה בגודל 1 על 1 סיימנו. אחרת, נבצע חיתוך שרירותי, נקבל 2 טבלאות קטנות יותר, נפעיל עליהם את הנחת האינדוקציה וסיימנו.
			===תרגיל===
	הוכיחו בעזרת אינדוקציה כי כל מצולע קמור (כלומר הצלע בין כל שני קודקודים נמצאת בפנים המצולע) בן <math>n \geq 3</math> צלעות ניתן לשילוש (כלומר ניתן לחלק אותו למשולשים)		הוכיחו בעזרת אינדוקציה כי כל מצולע קמור (כלומר הצלע בין כל שני קודקודים נמצאת בפנים המצולע) בן <math>n \geq 3</math> צלעות ניתן לשילוש (כלומר ניתן לחלק אותו למשולשים)
	ושיש בשילוש <math>n-3</math> אלכסונים.		ושיש בשילוש <math>n-3</math> אלכסונים.

אחיה בר-און: /* תרגיל: */

2021-07-05T06:15:13Z

תרגיל:

→ הגרסה הקודמת		גרסה מ־06:15, 5 ביולי 2021
שורה 188:		שורה 188:
	לכן, הטענה נכונה גם עבור <math>n+1</math> וסיימנו		לכן, הטענה נכונה גם עבור <math>n+1</math> וסיימנו

			=== תרגיל ===
			לכל <math>n</math> טבעי מתקיים: כל טבלה ריבועית בגודל <math>2^{n}\times2^{n}</math> שהוצאנו ממנה משבצת, ניתן לכסות ב "י" (3 משבצות בצורת האות יוד)

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

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

			צעד: נניח נכונות עבור <math>n</math> ונוכיח נוכונות עבור <math>n+1</math>. תהא טבלה בגודל <math>2^{n+1}\times2^{n+1}</math> שהוצאנו משבצת. את הטבלה הזאת נחלק ל 4 טבלאות קטנות יותר בגודל <math>2^{n}\times2^{n}</math> שאחת מהן חסרה משבצת. את הטבלה הזאת ניתן לכסות ב"יוד" ים לפי הנחת האינדוקציה. בנוסף ניתן להוציא "יוד" נוספת כך ששלושת הטבלאות האחרות יהיו חסרות משבצת אחת בדיוק ואז גם אותם ניתן לכסות ב"יוד" ים לפי הנחת האינדוקציה.

			מסקנה: לכל <math>n</math> טבעי מתקיים ש 3 מחלק את <math>\left(2^{n}\right)^{2}-1</math>.
	===תרגיל:===		===תרגיל:===
	הוכיחו בעזרת אינדוקציה כי כל מצולע קמור (כלומר הצלע בין כל שני קודקודים נמצאת בפנים המצולע) בן <math>n \geq 3</math> צלעות ניתן לשילוש (כלומר ניתן לחלק אותו למשולשים)		הוכיחו בעזרת אינדוקציה כי כל מצולע קמור (כלומר הצלע בין כל שני קודקודים נמצאת בפנים המצולע) בן <math>n \geq 3</math> צלעות ניתן לשילוש (כלומר ניתן לחלק אותו למשולשים)
שורה 199:		שורה 209:
	<math>n+1-(k-1)=n-k+2</math> ולכן מספר הצלעות של <math>M_2</math> הוא <math>n-k+3</math>.		<math>n+1-(k-1)=n-k+2</math> ולכן מספר הצלעות של <math>M_2</math> הוא <math>n-k+3</math>.
	כיוון ש <math>3\leq k,n-k+3\leq n+1</math> ניתן להפעיל את הנחת האינדוקציה על <math>M_1,M_2</math> ולהסיק כי <math>M_1,M_2</math> ניתן לשילוש ע"י <math>k-3,n-k+3 - 3</math> אלכסונים.		כיוון ש <math>3\leq k,n-k+3\leq n+1</math> ניתן להפעיל את הנחת האינדוקציה על <math>M_1,M_2</math> ולהסיק כי <math>M_1,M_2</math> ניתן לשילוש ע"י <math>k-3,n-k+3 - 3</math> אלכסונים.
	צירוף השילושים של <math>M_1,M_2</math> יתן שילוש של <math>M</math> עם <math>(k-3) + (n-k)+1=(n+1)-3 </math> אלכסונים כנדרש.		צירוף השילושים של <math>M_1,M_2</math> יתן שילוש של <math>M</math> עם <math>(k-3) + (n-k)+1=(n+1)-3 </math> אלכסונים כנדרש.


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

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

2021-06-29T11:51:33Z

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

→ הגרסה הקודמת		גרסה מ־11:51, 29 ביוני 2021
שורה 11:		שורה 11:
	בוא נחשוב.. הוכחנו באופן ישיר כי הטענה נכונה עבור <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>

	דוגמא:		====דוגמא====
	נוכיח באינדוקציה כי הטענה <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\in \mathbb{N} </math> טבעי		נכונה לכל <math>n\in \mathbb{N} </math> טבעי
שורה 37:		שורה 37:


	דוגמא ~~נוספת:~~		====דוגמא====

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

	שזה הטענה עבור <math>n+1</math> וסיימנו.		שזה הטענה עבור <math>n+1</math> וסיימנו.
			==== תרגיל ====
			הוכיחו שלכל <math>n</math> טבעי מתקיים <math>\sum_{k=1}^{n}(2k-1)=n^{2}</math>
	=== לפעמים כדאי להניח הנחות חזקות יותר ===		=== לפעמים כדאי להניח הנחות חזקות יותר ===
	תרגיל:		תרגיל:

אחיה בר-און: /* הכללה פשוטה 1 */

2021-06-29T11:50:05Z

הכללה פשוטה 1

→ הגרסה הקודמת		גרסה מ־11:50, 29 ביוני 2021
שורה 99:		שורה 99:

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

			==== תרגיל ====
			מצאו עבור אילו <math>n</math>ים מתקיים <math>n^{2}<2^{n}</math>

	===הכללה פשוטה 2 ===		===הכללה פשוטה 2 ===

אחיה בר-און: /* תרגילים יותר מעניינים (לא בסגנון "בני גורן". אם יש את הרקע המספק) */

2021-06-29T11:47:21Z

תרגילים יותר מעניינים (לא בסגנון "בני גורן". אם יש את הרקע המספק)

→ הגרסה הקודמת		גרסה מ־11:47, 29 ביוני 2021
שורה 132:		שורה 132:

	עוד תרגילים [[מכינה למתמטיקה קיץ תשעב/תרגילים/4]]		עוד תרגילים [[מכינה למתמטיקה קיץ תשעב/תרגילים/4]]
			[https://www.weizmann.ac.il/sci-tea/benari/sites/sci-tea.benari/files/uploads/softwareAndLearningMaterials/induction-he.pdf מדריך אינדוקציה של מכון ויצמן]
	== תרגילים יותר מעניינים (לא בסגנון "בני גורן". אם יש את הרקע המספק)==		== תרגילים יותר מעניינים (לא בסגנון "בני גורן". אם יש את הרקע המספק)==
	===תרגיל ===		===תרגיל ===

אחיה בר-און: /* תרגילים יותר מעניינים (לא בסגנון "בני גורן") */

2021-06-21T09:20:24Z

תרגילים יותר מעניינים (לא בסגנון "בני גורן")

→ הגרסה הקודמת		גרסה מ־09:20, 21 ביוני 2021
שורה 132:		שורה 132:

	עוד תרגילים [[מכינה למתמטיקה קיץ תשעב/תרגילים/4]]		עוד תרגילים [[מכינה למתמטיקה קיץ תשעב/תרגילים/4]]
	== תרגילים יותר מעניינים (לא בסגנון "בני גורן")==		== תרגילים יותר מעניינים (לא בסגנון "בני גורן". אם יש את הרקע המספק)==
	===תרגיל ===		===תרגיל ===
	יהא <math>A</math> פסוק. נגדיר בעזרת אינדוקציה פסוקים:		יהא <math>A</math> פסוק. נגדיר בעזרת אינדוקציה פסוקים:

אחיה בר-און ב־09:19, 21 ביוני 2021

2021-06-21T09:19:34Z

הצגת שינויים

אחיה בר-און: /* תרגילים יותר מעניינים */

2021-06-21T09:16:43Z

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

→ הגרסה הקודמת		גרסה מ־09:16, 21 ביוני 2021
שורה 190:		שורה 190:
	הערה: אפשר לעשות אינדוקציה הנקראת אינדוקציה טרנספניטית על קבוצות כלשהן (לאו דווקא בנות מניה)		הערה: אפשר לעשות אינדוקציה הנקראת אינדוקציה טרנספניטית על קבוצות כלשהן (לאו דווקא בנות מניה)

	== תרגילים יותר מעניינים ==		עוד תרגילים [[מכינה למתמטיקה קיץ תשעב/תרגילים/4]]
			== תרגילים יותר מעניינים (לא בסגנון "בני גורן")==
	===תרגיל ===		===תרגיל ===
	יהא <math>A</math> פסוק. נגדיר בעזרת אינדוקציה פסוקים:		יהא <math>A</math> פסוק. נגדיר בעזרת אינדוקציה פסוקים:

אריאל: /* לפעמים כדאי להניח הנחות חזקות יותר */

2019-07-15T09:18:53Z

לפעמים כדאי להניח הנחות חזקות יותר

→ הגרסה הקודמת		גרסה מ־09:18, 15 ביולי 2019
שורה 57:		שורה 57:
	תרגיל:		תרגיל:

	נגדיר <math>a_0 =0 , a_{n+1}=a_n^2 +1/4</math>/		נגדיר <math>a_0 =0 , a_{n+1}=a_n^2 +1/4</math>.

	הוכח כי לכל n מתקיים <math>a_n<1</math>		הוכח כי לכל n מתקיים <math>a_n<1</math>