איך מוכיחים טענה באינדוקציה?

כן

בודקים את נכונות הטענה עבור n=1
מניחים שהטענה נכונה עבור n=k, k מספר טבעי כלשהו
מוכיחים שהטענה נכונה עבור n=k+1

https://youtu.be/c0_36p2kopi?si=tk_nt-hqydwl4zsy

רק תיזהר להגיע למסקנה שכל פתיתי השלג בעולם הם זהים ;)

יש 3 שלבים:
בסיס האינדוקציה: הטענה נכונה עבור המקרה הבסיסי שאפשר להתקדם ממנו. למשל n=0, צומת בודד בגרף, ווטאבר.
הנחת האינדוקציה: מניחים שעבור כל המקרים הקודמים או בפרט המקרה שבדיוק קדם למשל מקרה n-1 או כל n-1 המקרים שקרו הטענה נכונה עבורם.
צעד האינדוקציה: בעזרת ההנחה, מוכיחים שהטענה נכונה גם לדבר הנוכחי. למשל נכונה עבור האיבר הn לפי זה שהיא נכונה עבור האיבר הn-1.

וכך מוכיחים שבעצם ניתן להתקדם ממקרה הבסיס לכל מקרה, ולכן הטענה נכונה להכל