Slides til 4.1 og 4.2: Eksempler på feil i induksjonsbevis

Slides til 4.1 og 4.2:

Eksempler på feil i induksjonsbevis

Andreas Leopold Knutsen February 9, 2010

Eks. 1: Finn feilen

Fibonaccitallene F₁, F₂, F₃, . . . er denert rekursivt ved:

F₀ = 0, F₁ = 1, og F_n = F_n−1 + F_n−2 for n ≥ 2. Påstand: Alle Fibonaccitall er partall

"Bevis" ved sterk induksjon: La P(n) være påstanden F_n er partall. Vil vise ∀(n ≥ 0)P(n).

GRUNNTRINN: F₀ = 0 er partall, så P(0) er sann.

INDUKSJONSTRINN: Anta F₀, F₁, . . . , F_k partall, for en k ≥ 0. Da er

F_k+1 = F_k + F_k−1 = partall + partall = partall, slik at P(k + 1) er sann.

Har derfor vist at alle Fibonaccitall er partall.

Eks. 1: Finn feilen

Fibonaccitallene F₁, F₂, F₃, . . . er denert rekursivt ved:

F₀ = 0, F₁ = 1, og F_n = F_n−1 + F_n−2 for n ≥ 2. Påstand: Alle Fibonaccitall er partall

"Bevis" ved sterk induksjon: La P(n) være påstanden F_n er partall. Vil vise ∀(n ≥ 0)P(n).

GRUNNTRINN: F₀ = 0 er partall, så P(0) er sann.

INDUKSJONSTRINN: Anta F₀, F₁, . . . , F_k partall, for en k ≥ 0. Da er

F_k+1 = F_k + F_k−1 = partall + partall = partall, slik at P(k + 1) er sann.

Har derfor vist at alle Fibonaccitall er partall.

Eks. 1: Finn feilen

Fibonaccitallene F₁, F₂, F₃, . . . er denert rekursivt ved:

F₀ = 0, F₁ = 1, og F_n = F_n−1 + F_n−2 for n ≥ 2. Påstand: Alle Fibonaccitall er partall

"Bevis" ved sterk induksjon: La P(n) være påstanden F_n er partall. Vil vise ∀(n ≥ 0)P(n).

GRUNNTRINN: F₀ = 0 er partall, så P(0) er sann.

INDUKSJONSTRINN: Anta F₀, F₁, . . . , F_k partall, for en k ≥ 0. Da er

F_k+1 = F_k + F_k−1 = partall + partall = partall, slik at P(k + 1) er sann.

Har derfor vist at alle Fibonaccitall er partall.

Eks. 1: Finn feilen

Fibonaccitallene F₁, F₂, F₃, . . . er denert rekursivt ved:

F₀ = 0, F₁ = 1, og F_n = F_n−1 + F_n−2 for n ≥ 2. Påstand: Alle Fibonaccitall er partall

"Bevis" ved sterk induksjon: La P(n) være påstanden F_n er partall. Vil vise ∀(n ≥ 0)P(n).

GRUNNTRINN: F₀ = 0 er partall, så P(0) er sann.

INDUKSJONSTRINN: Anta F₀, F₁, . . . , F_k partall, for en k ≥ 0. Da er

F_k+1 = F_k + F_k−1 = partall + partall = partall, slik at P(k + 1) er sann.

Har derfor vist at alle Fibonaccitall er partall.

Eks. 1: Finn feilen

Fibonaccitallene F₁, F₂, F₃, . . . er denert rekursivt ved:

F₀ = 0, F₁ = 1, og F_n = F_n−1 + F_n−2 for n ≥ 2. Påstand: Alle Fibonaccitall er partall

"Bevis" ved sterk induksjon: La P(n) være påstanden F_n er partall. Vil vise ∀(n ≥ 0)P(n).

GRUNNTRINN: F₀ = 0 er partall, så P(0) er sann.

INDUKSJONSTRINN: Anta F₀, F₁, . . . , F_k partall, for en k ≥ 0. Da er

F_k+1 = F_k + F_k−1 = partall + partall = partall, slik at P(k + 1) er sann.

Har derfor vist at alle Fibonaccitall er partall.

Eks. 1: Finn feilen

Fibonaccitallene F₁, F₂, F₃, . . . er denert rekursivt ved:

F₀ = 0, F₁ = 1, og F_n = F_n−1 + F_n−2 for n ≥ 2. Påstand: Alle Fibonaccitall er partall

"Bevis" ved sterk induksjon: La P(n) være påstanden F_n er partall. Vil vise ∀(n ≥ 0)P(n).

GRUNNTRINN: F₀ = 0 er partall, så P(0) er sann.

INDUKSJONSTRINN: Anta F₀, F₁, . . . , F_k partall, for en k ≥ 0. Da er

F_k+1 = F_k + F_k−1 = partall + partall = partall, slik at P(k + 1) er sann.

Har derfor vist at alle Fibonaccitall er partall.

Eks. 1: Finn feilen

Fibonaccitallene F₁, F₂, F₃, . . . er denert rekursivt ved:

F₀ = 0, F₁ = 1, og F_n = F_n−1 + F_n−2 for n ≥ 2. Påstand: Alle Fibonaccitall er partall

"Bevis" ved sterk induksjon: La P(n) være påstanden F_n er partall. Vil vise ∀(n ≥ 0)P(n).

GRUNNTRINN: F₀ = 0 er partall, så P(0) er sann.

INDUKSJONSTRINN: Anta F₀, F₁, . . . , F_k partall, for en k ≥ 0. Da er

F_k+1 = F_k + F_k−1 = partall + partall = partall, slik at P(k + 1) er sann.

Har derfor vist at alle Fibonaccitall er partall.

Eks. 1: Finn feilen

Fibonaccitallene F₁, F₂, F₃, . . . er denert rekursivt ved:

F₀ = 0, F₁ = 1, og F_n = F_n−1 + F_n−2 for n ≥ 2. Påstand: Alle Fibonaccitall er partall

"Bevis" ved sterk induksjon: La P(n) være påstanden F_n er partall. Vil vise ∀(n ≥ 0)P(n).

GRUNNTRINN: F₀ = 0 er partall, så P(0) er sann.

INDUKSJONSTRINN: Anta F₀, F₁, . . . , F_k partall, for en k ≥ 0. Da er

F_k+1 = F_k + F_k−1 = partall + partall = partall, slik at P(k + 1) er sann.

Har derfor vist at alle Fibonaccitall er partall.

Eks. 1: Finn feilen

Fibonaccitallene F₁, F₂, F₃, . . . er denert rekursivt ved:

F₀ = 0, F₁ = 1, og F_n = F_n−1 + F_n−2 for n ≥ 2. Påstand: Alle Fibonaccitall er partall

"Bevis" ved sterk induksjon: La P(n) være påstanden F_n er partall. Vil vise ∀(n ≥ 0)P(n).

GRUNNTRINN: F₀ = 0 er partall, så P(0) er sann.

INDUKSJONSTRINN: Anta F₀, F₁, . . . , F_k partall, for en k ≥ 0. Da er

F_k+1 = F_k + F_k−1 = partall + partall = partall, slik at P(k + 1) er sann.

Har derfor vist at alle Fibonaccitall er partall.

Eks. 1: Finn feilen

Fibonaccitallene F₁, F₂, F₃, . . . er denert rekursivt ved:

F₀ = 0, F₁ = 1, og F_n = F_n−1 + F_n−2 for n ≥ 2. Påstand: Alle Fibonaccitall er partall

"Bevis" ved sterk induksjon: La P(n) være påstanden F_n er partall. Vil vise ∀(n ≥ 0)P(n).

GRUNNTRINN: F₀ = 0 er partall, så P(0) er sann.

INDUKSJONSTRINN: Anta F₀, F₁, . . . , F_k partall, for en k ≥ 0. Da er

F_k+1 = F_k + F_k−1 = partall + partall = partall, slik at P(k + 1) er sann.

Har derfor vist at alle Fibonaccitall er partall.

Eks. 2: Finn feilen

(Riktig) Påstand: Alle heltall n ≥ 2 har entydig primtallsfaktorisering (Thm. 1 i 3.5)

"Bevis" ved sterk induksjon: La P(n) være påstanden n har entydig primtallsfaktorisering.

Vil vise ∀(n ≥ 2)P(n).

GRUNNTRINN: P(2) holder trivielt.

INDUKSJONSTRINN: Anta P(n) holder for alle

2 ≤ n ≤ k for et heltall k ≥ 2, dvs. anta at alle heltall n slik at 2 ≤ n ≤ k har entydig primtallsfaktorisering.

Vil vise k + 1 har entydig primtallsfaktorisering.

Dersom k + 1 er primtall, er dettte trivielt oppfylt.

Dersom k + 1 ikke er primtall, betyr det per denisjon at k + 1 = a · b der a og b er heltall slik at

2 ≤ a, b < k = 1.

Induksjonshypotesen gir at a og b har entydig

primtallsfaktorisering. Ergo har også k + 1 entydig primtallsfaktorisering.

Har derfor vist at alle heltall n ≥ 2 har entydig primtallsfaktorisering.

Eks. 2: Finn feilen

(Riktig) Påstand: Alle heltall n ≥ 2 har entydig primtallsfaktorisering (Thm. 1 i 3.5)

"Bevis" ved sterk induksjon: La P(n) være påstanden n har entydig primtallsfaktorisering.

Vil vise ∀(n ≥ 2)P(n).

GRUNNTRINN: P(2) holder trivielt.

INDUKSJONSTRINN: Anta P(n) holder for alle

2 ≤ n ≤ k for et heltall k ≥ 2, dvs. anta at alle heltall n slik at 2 ≤ n ≤ k har entydig primtallsfaktorisering.

Vil vise k + 1 har entydig primtallsfaktorisering.

Dersom k + 1 er primtall, er dettte trivielt oppfylt.

Dersom k + 1 ikke er primtall, betyr det per denisjon at k + 1 = a · b der a og b er heltall slik at

2 ≤ a, b < k = 1.

Induksjonshypotesen gir at a og b har entydig

primtallsfaktorisering. Ergo har også k + 1 entydig primtallsfaktorisering.

Har derfor vist at alle heltall n ≥ 2 har entydig primtallsfaktorisering.

Eks. 2: Finn feilen

(Riktig) Påstand: Alle heltall n ≥ 2 har entydig primtallsfaktorisering (Thm. 1 i 3.5)

"Bevis" ved sterk induksjon: La P(n) være påstanden n har entydig primtallsfaktorisering.

Vil vise ∀(n ≥ 2)P(n).

GRUNNTRINN: P(2) holder trivielt.

INDUKSJONSTRINN: Anta P(n) holder for alle

2 ≤ n ≤ k for et heltall k ≥ 2, dvs. anta at alle heltall n slik at 2 ≤ n ≤ k har entydig primtallsfaktorisering.

Vil vise k + 1 har entydig primtallsfaktorisering.

Dersom k + 1 er primtall, er dettte trivielt oppfylt.

Dersom k + 1 ikke er primtall, betyr det per denisjon at k + 1 = a · b der a og b er heltall slik at

2 ≤ a, b < k = 1.

Induksjonshypotesen gir at a og b har entydig

primtallsfaktorisering. Ergo har også k + 1 entydig primtallsfaktorisering.

Har derfor vist at alle heltall n ≥ 2 har entydig primtallsfaktorisering.

Eks. 2: Finn feilen

(Riktig) Påstand: Alle heltall n ≥ 2 har entydig primtallsfaktorisering (Thm. 1 i 3.5)

"Bevis" ved sterk induksjon: La P(n) være påstanden n har entydig primtallsfaktorisering.

Vil vise ∀(n ≥ 2)P(n).

GRUNNTRINN: P(2) holder trivielt.

INDUKSJONSTRINN: Anta P(n) holder for alle

2 ≤ n ≤ k for et heltall k ≥ 2, dvs. anta at alle heltall n slik at 2 ≤ n ≤ k har entydig primtallsfaktorisering.

Vil vise k + 1 har entydig primtallsfaktorisering.

Dersom k + 1 er primtall, er dettte trivielt oppfylt.

Dersom k + 1 ikke er primtall, betyr det per denisjon at k + 1 = a · b der a og b er heltall slik at

2 ≤ a, b < k = 1.

Induksjonshypotesen gir at a og b har entydig

primtallsfaktorisering. Ergo har også k + 1 entydig primtallsfaktorisering.

Har derfor vist at alle heltall n ≥ 2 har entydig primtallsfaktorisering.

Eks. 2: Finn feilen

(Riktig) Påstand: Alle heltall n ≥ 2 har entydig primtallsfaktorisering (Thm. 1 i 3.5)

"Bevis" ved sterk induksjon: La P(n) være påstanden n har entydig primtallsfaktorisering.

Vil vise ∀(n ≥ 2)P(n).

GRUNNTRINN: P(2) holder trivielt.

INDUKSJONSTRINN: Anta P(n) holder for alle

2 ≤ n ≤ k for et heltall k ≥ 2, dvs. anta at alle heltall n slik at 2 ≤ n ≤ k har entydig primtallsfaktorisering.

Vil vise k + 1 har entydig primtallsfaktorisering.

Dersom k + 1 er primtall, er dettte trivielt oppfylt.

Dersom k + 1 ikke er primtall, betyr det per denisjon at k + 1 = a · b der a og b er heltall slik at

2 ≤ a, b < k = 1.

Induksjonshypotesen gir at a og b har entydig

primtallsfaktorisering. Ergo har også k + 1 entydig primtallsfaktorisering.

Har derfor vist at alle heltall n ≥ 2 har entydig primtallsfaktorisering.

Eks. 2: Finn feilen

(Riktig) Påstand: Alle heltall n ≥ 2 har entydig primtallsfaktorisering (Thm. 1 i 3.5)

"Bevis" ved sterk induksjon: La P(n) være påstanden n har entydig primtallsfaktorisering.

Vil vise ∀(n ≥ 2)P(n).

GRUNNTRINN: P(2) holder trivielt.

INDUKSJONSTRINN: Anta P(n) holder for alle

2 ≤ n ≤ k for et heltall k ≥ 2, dvs. anta at alle heltall n slik at 2 ≤ n ≤ k har entydig primtallsfaktorisering.

Vil vise k + 1 har entydig primtallsfaktorisering.

Dersom k + 1 er primtall, er dettte trivielt oppfylt.

Dersom k + 1 ikke er primtall, betyr det per denisjon at k + 1 = a · b der a og b er heltall slik at

2 ≤ a, b < k = 1.

Induksjonshypotesen gir at a og b har entydig

primtallsfaktorisering. Ergo har også k + 1 entydig primtallsfaktorisering.

Har derfor vist at alle heltall n ≥ 2 har entydig primtallsfaktorisering.

Eks. 2: Finn feilen

(Riktig) Påstand: Alle heltall n ≥ 2 har entydig primtallsfaktorisering (Thm. 1 i 3.5)

"Bevis" ved sterk induksjon: La P(n) være påstanden n har entydig primtallsfaktorisering.

Vil vise ∀(n ≥ 2)P(n).

GRUNNTRINN: P(2) holder trivielt.

INDUKSJONSTRINN: Anta P(n) holder for alle

2 ≤ n ≤ k for et heltall k ≥ 2, dvs. anta at alle heltall n slik at 2 ≤ n ≤ k har entydig primtallsfaktorisering.

Vil vise k + 1 har entydig primtallsfaktorisering.

Dersom k + 1 er primtall, er dettte trivielt oppfylt.

Dersom k + 1 ikke er primtall, betyr det per denisjon at k + 1 = a · b der a og b er heltall slik at

2 ≤ a, b < k = 1.

Induksjonshypotesen gir at a og b har entydig

primtallsfaktorisering. Ergo har også k + 1 entydig primtallsfaktorisering.

Har derfor vist at alle heltall n ≥ 2 har entydig primtallsfaktorisering.

Eks. 2: Finn feilen

(Riktig) Påstand: Alle heltall n ≥ 2 har entydig primtallsfaktorisering (Thm. 1 i 3.5)

"Bevis" ved sterk induksjon: La P(n) være påstanden n har entydig primtallsfaktorisering.

Vil vise ∀(n ≥ 2)P(n).

GRUNNTRINN: P(2) holder trivielt.

INDUKSJONSTRINN: Anta P(n) holder for alle

2 ≤ n ≤ k for et heltall k ≥ 2, dvs. anta at alle heltall n slik at 2 ≤ n ≤ k har entydig primtallsfaktorisering.

Vil vise k + 1 har entydig primtallsfaktorisering.

Dersom k + 1 er primtall, er dettte trivielt oppfylt.

Dersom k + 1 ikke er primtall, betyr det per denisjon at k + 1 = a · b der a og b er heltall slik at

2 ≤ a, b < k = 1.

Induksjonshypotesen gir at a og b har entydig

primtallsfaktorisering. Ergo har også k + 1 entydig primtallsfaktorisering.

Har derfor vist at alle heltall n ≥ 2 har entydig primtallsfaktorisering.

Eks. 2: Finn feilen

(Riktig) Påstand: Alle heltall n ≥ 2 har entydig primtallsfaktorisering (Thm. 1 i 3.5)

"Bevis" ved sterk induksjon: La P(n) være påstanden n har entydig primtallsfaktorisering.

Vil vise ∀(n ≥ 2)P(n).

GRUNNTRINN: P(2) holder trivielt.

INDUKSJONSTRINN: Anta P(n) holder for alle

2 ≤ n ≤ k for et heltall k ≥ 2, dvs. anta at alle heltall n slik at 2 ≤ n ≤ k har entydig primtallsfaktorisering.

Vil vise k + 1 har entydig primtallsfaktorisering.

Dersom k + 1 er primtall, er dettte trivielt oppfylt.

Dersom k + 1 ikke er primtall, betyr det per denisjon at k + 1 = a · b der a og b er heltall slik at

2 ≤ a, b < k = 1.

Induksjonshypotesen gir at a og b har entydig

primtallsfaktorisering. Ergo har også k + 1 entydig primtallsfaktorisering.

Har derfor vist at alle heltall n ≥ 2 har entydig primtallsfaktorisering.

Eks. 2: Finn feilen

(Riktig) Påstand: Alle heltall n ≥ 2 har entydig primtallsfaktorisering (Thm. 1 i 3.5)

"Bevis" ved sterk induksjon: La P(n) være påstanden n har entydig primtallsfaktorisering.

Vil vise ∀(n ≥ 2)P(n).

GRUNNTRINN: P(2) holder trivielt.

INDUKSJONSTRINN: Anta P(n) holder for alle

2 ≤ n ≤ k for et heltall k ≥ 2, dvs. anta at alle heltall n slik at 2 ≤ n ≤ k har entydig primtallsfaktorisering.

Vil vise k + 1 har entydig primtallsfaktorisering.

Dersom k + 1 er primtall, er dettte trivielt oppfylt.

Dersom k + 1 ikke er primtall, betyr det per denisjon at k + 1 = a · b der a og b er heltall slik at

2 ≤ a, b < k = 1.

Induksjonshypotesen gir at a og b har entydig

primtallsfaktorisering. Ergo har også k + 1 entydig primtallsfaktorisering.

Har derfor vist at alle heltall n ≥ 2 har entydig primtallsfaktorisering.

Eks. 2: Finn feilen

(Riktig) Påstand: Alle heltall n ≥ 2 har entydig primtallsfaktorisering (Thm. 1 i 3.5)

"Bevis" ved sterk induksjon: La P(n) være påstanden n har entydig primtallsfaktorisering.

Vil vise ∀(n ≥ 2)P(n).

GRUNNTRINN: P(2) holder trivielt.

INDUKSJONSTRINN: Anta P(n) holder for alle

2 ≤ n ≤ k for et heltall k ≥ 2, dvs. anta at alle heltall n slik at 2 ≤ n ≤ k har entydig primtallsfaktorisering.

Vil vise k + 1 har entydig primtallsfaktorisering.

Dersom k + 1 er primtall, er dettte trivielt oppfylt.

Dersom k + 1 ikke er primtall, betyr det per denisjon at k + 1 = a · b der a og b er heltall slik at

2 ≤ a, b < k = 1.

Induksjonshypotesen gir at a og b har entydig

primtallsfaktorisering. Ergo har også k + 1 entydig primtallsfaktorisering.

Har derfor vist at alle heltall n ≥ 2 har entydig primtallsfaktorisering.

Eks. 2: Finn feilen

(Riktig) Påstand: Alle heltall n ≥ 2 har entydig primtallsfaktorisering (Thm. 1 i 3.5)

"Bevis" ved sterk induksjon: La P(n) være påstanden n har entydig primtallsfaktorisering.

Vil vise ∀(n ≥ 2)P(n).

GRUNNTRINN: P(2) holder trivielt.

INDUKSJONSTRINN: Anta P(n) holder for alle

2 ≤ n ≤ k for et heltall k ≥ 2, dvs. anta at alle heltall n slik at 2 ≤ n ≤ k har entydig primtallsfaktorisering.

Vil vise k + 1 har entydig primtallsfaktorisering.

Dersom k + 1 er primtall, er dettte trivielt oppfylt.

Dersom k + 1 ikke er primtall, betyr det per denisjon at k + 1 = a · b der a og b er heltall slik at

2 ≤ a, b < k = 1.

Induksjonshypotesen gir at a og b har entydig

primtallsfaktorisering. Ergo har også k + 1 entydig primtallsfaktorisering.

Har derfor vist at alle heltall n ≥ 2 har entydig primtallsfaktorisering.

Eks. 2: Finn feilen

(Riktig) Påstand: Alle heltall n ≥ 2 har entydig primtallsfaktorisering (Thm. 1 i 3.5)

"Bevis" ved sterk induksjon: La P(n) være påstanden n har entydig primtallsfaktorisering.

Vil vise ∀(n ≥ 2)P(n).

GRUNNTRINN: P(2) holder trivielt.

INDUKSJONSTRINN: Anta P(n) holder for alle

2 ≤ n ≤ k for et heltall k ≥ 2, dvs. anta at alle heltall n slik at 2 ≤ n ≤ k har entydig primtallsfaktorisering.

Vil vise k + 1 har entydig primtallsfaktorisering.

Dersom k + 1 er primtall, er dettte trivielt oppfylt.

Dersom k + 1 ikke er primtall, betyr det per denisjon at k + 1 = a · b der a og b er heltall slik at

2 ≤ a, b < k = 1.

Induksjonshypotesen gir at a og b har entydig

primtallsfaktorisering. Ergo har også k + 1 entydig primtallsfaktorisering.

Har derfor vist at alle heltall n ≥ 2 har entydig primtallsfaktorisering.

Eks. 3: Finn feilen

Påstand: Alle nyfødte barn har samme øyenfarge.

"Bevis" ved svak induksjon: Anta at vi har n nyfødte barn. Påstanden er opplagt sann for n = 1.

Anta at påstanden er sann for n = k nyfødte barn.

Betrakt en mengde av k + 1 nyfødte barn.

Vi kan anta ved induksjon at i mengden L av k barn til venstre i tegningen, har alle barn samme øyenfarge.

Likeledes kan vi anta at alle k barn i mengden R til

høyre har samme øyenfarge. Men da har selvfølgelig alle k + 1 barna samme øyenfarge, for barnet helt til venstre og barnet helt til høyre har samme øyenfarge som barna i mellom.

Dermed har vi vist ved induksjon at i en mengde

bestående av n nyfødte barn, har alle samme øyenfarge, uansett hva n er. Derfor har alle nyfødte barn samme øyenfarge.

Eks. 3: Finn feilen

Påstand: Alle nyfødte barn har samme øyenfarge.

"Bevis" ved svak induksjon: Anta at vi har n nyfødte barn. Påstanden er opplagt sann for n = 1.

Anta at påstanden er sann for n = k nyfødte barn.

Betrakt en mengde av k + 1 nyfødte barn.

Vi kan anta ved induksjon at i mengden L av k barn til venstre i tegningen, har alle barn samme øyenfarge.

Likeledes kan vi anta at alle k barn i mengden R til

høyre har samme øyenfarge. Men da har selvfølgelig alle k + 1 barna samme øyenfarge, for barnet helt til venstre og barnet helt til høyre har samme øyenfarge som barna i mellom.

Dermed har vi vist ved induksjon at i en mengde

bestående av n nyfødte barn, har alle samme øyenfarge, uansett hva n er. Derfor har alle nyfødte barn samme øyenfarge.

Eks. 3: Finn feilen

Påstand: Alle nyfødte barn har samme øyenfarge.

"Bevis" ved svak induksjon: Anta at vi har n nyfødte barn. Påstanden er opplagt sann for n = 1.

Anta at påstanden er sann for n = k nyfødte barn.

Betrakt en mengde av k + 1 nyfødte barn.

Vi kan anta ved induksjon at i mengden L av k barn til venstre i tegningen, har alle barn samme øyenfarge.

Likeledes kan vi anta at alle k barn i mengden R til

høyre har samme øyenfarge. Men da har selvfølgelig alle k + 1 barna samme øyenfarge, for barnet helt til venstre og barnet helt til høyre har samme øyenfarge som barna i mellom.

Dermed har vi vist ved induksjon at i en mengde

bestående av n nyfødte barn, har alle samme øyenfarge, uansett hva n er. Derfor har alle nyfødte barn samme øyenfarge.

Eks. 3: Finn feilen

Påstand: Alle nyfødte barn har samme øyenfarge.

"Bevis" ved svak induksjon: Anta at vi har n nyfødte barn. Påstanden er opplagt sann for n = 1.

Anta at påstanden er sann for n = k nyfødte barn.

Betrakt en mengde av k + 1 nyfødte barn.

Vi kan anta ved induksjon at i mengden L av k barn til venstre i tegningen, har alle barn samme øyenfarge.

Likeledes kan vi anta at alle k barn i mengden R til

høyre har samme øyenfarge. Men da har selvfølgelig alle k + 1 barna samme øyenfarge, for barnet helt til venstre og barnet helt til høyre har samme øyenfarge som barna i mellom.

Dermed har vi vist ved induksjon at i en mengde

bestående av n nyfødte barn, har alle samme øyenfarge, uansett hva n er. Derfor har alle nyfødte barn samme øyenfarge.

Eks. 3: Finn feilen

Påstand: Alle nyfødte barn har samme øyenfarge.

"Bevis" ved svak induksjon: Anta at vi har n nyfødte barn. Påstanden er opplagt sann for n = 1.

Anta at påstanden er sann for n = k nyfødte barn.

Betrakt en mengde av k + 1 nyfødte barn.

Vi kan anta ved induksjon at i mengden L av k barn til venstre i tegningen, har alle barn samme øyenfarge.

Likeledes kan vi anta at alle k barn i mengden R til

høyre har samme øyenfarge. Men da har selvfølgelig alle k + 1 barna samme øyenfarge, for barnet helt til venstre og barnet helt til høyre har samme øyenfarge som barna i mellom.

Dermed har vi vist ved induksjon at i en mengde

bestående av n nyfødte barn, har alle samme øyenfarge, uansett hva n er. Derfor har alle nyfødte barn samme øyenfarge.

Eks. 3: Finn feilen

Påstand: Alle nyfødte barn har samme øyenfarge.

"Bevis" ved svak induksjon: Anta at vi har n nyfødte barn. Påstanden er opplagt sann for n = 1.

Anta at påstanden er sann for n = k nyfødte barn.

Betrakt en mengde av k + 1 nyfødte barn.

Vi kan anta ved induksjon at i mengden L av k barn til venstre i tegningen, har alle barn samme øyenfarge.

Likeledes kan vi anta at alle k barn i mengden R til

høyre har samme øyenfarge. Men da har selvfølgelig alle k + 1 barna samme øyenfarge, for barnet helt til venstre og barnet helt til høyre har samme øyenfarge som barna i mellom.

Dermed har vi vist ved induksjon at i en mengde

bestående av n nyfødte barn, har alle samme øyenfarge, uansett hva n er. Derfor har alle nyfødte barn samme øyenfarge.

Eks. 3: Finn feilen

Påstand: Alle nyfødte barn har samme øyenfarge.

"Bevis" ved svak induksjon: Anta at vi har n nyfødte barn. Påstanden er opplagt sann for n = 1.

Anta at påstanden er sann for n = k nyfødte barn.

Betrakt en mengde av k + 1 nyfødte barn.

Vi kan anta ved induksjon at i mengden L av k barn til venstre i tegningen, har alle barn samme øyenfarge.

Likeledes kan vi anta at alle k barn i mengden R til

høyre har samme øyenfarge. Men da har selvfølgelig alle k + 1 barna samme øyenfarge, for barnet helt til venstre og barnet helt til høyre har samme øyenfarge som barna i mellom.

Dermed har vi vist ved induksjon at i en mengde

bestående av n nyfødte barn, har alle samme øyenfarge, uansett hva n er. Derfor har alle nyfødte barn samme øyenfarge.

Eks. 3: Finn feilen

Påstand: Alle nyfødte barn har samme øyenfarge.

"Bevis" ved svak induksjon: Anta at vi har n nyfødte barn. Påstanden er opplagt sann for n = 1.

Anta at påstanden er sann for n = k nyfødte barn.

Betrakt en mengde av k + 1 nyfødte barn.

Vi kan anta ved induksjon at i mengden L av k barn til venstre i tegningen, har alle barn samme øyenfarge.

Likeledes kan vi anta at alle k barn i mengden R til

høyre har samme øyenfarge. Men da har selvfølgelig alle k + 1 barna samme øyenfarge, for barnet helt til venstre og barnet helt til høyre har samme øyenfarge som barna i mellom.

Dermed har vi vist ved induksjon at i en mengde

bestående av n nyfødte barn, har alle samme øyenfarge, uansett hva n er. Derfor har alle nyfødte barn samme øyenfarge.

Eks. 3: Finn feilen

Påstand: Alle nyfødte barn har samme øyenfarge.

"Bevis" ved svak induksjon: Anta at vi har n nyfødte barn. Påstanden er opplagt sann for n = 1.

Anta at påstanden er sann for n = k nyfødte barn.

Betrakt en mengde av k + 1 nyfødte barn.

Vi kan anta ved induksjon at i mengden L av k barn til venstre i tegningen, har alle barn samme øyenfarge.

Likeledes kan vi anta at alle k barn i mengden R til

høyre har samme øyenfarge. Men da har selvfølgelig alle k + 1 barna samme øyenfarge, for barnet helt til venstre og barnet helt til høyre har samme øyenfarge som barna i mellom.

Dermed har vi vist ved induksjon at i en mengde

bestående av n nyfødte barn, har alle samme øyenfarge, uansett hva n er. Derfor har alle nyfødte barn samme øyenfarge.

Eks. 3: Finn feilen

Påstand: Alle nyfødte barn har samme øyenfarge.

"Bevis" ved svak induksjon: Anta at vi har n nyfødte barn. Påstanden er opplagt sann for n = 1.

Anta at påstanden er sann for n = k nyfødte barn.

Betrakt en mengde av k + 1 nyfødte barn.

Vi kan anta ved induksjon at i mengden L av k barn til venstre i tegningen, har alle barn samme øyenfarge.

Likeledes kan vi anta at alle k barn i mengden R til

høyre har samme øyenfarge. Men da har selvfølgelig alle k + 1 barna samme øyenfarge, for barnet helt til venstre og barnet helt til høyre har samme øyenfarge som barna i mellom.

Dermed har vi vist ved induksjon at i en mengde

bestående av n nyfødte barn, har alle samme øyenfarge, uansett hva n er. Derfor har alle nyfødte barn samme øyenfarge.

Eks. 3: Finn feilen

Påstand: Alle nyfødte barn har samme øyenfarge.

"Bevis" ved svak induksjon: Anta at vi har n nyfødte barn. Påstanden er opplagt sann for n = 1.

Anta at påstanden er sann for n = k nyfødte barn.

Betrakt en mengde av k + 1 nyfødte barn.

Vi kan anta ved induksjon at i mengden L av k barn til venstre i tegningen, har alle barn samme øyenfarge.

Likeledes kan vi anta at alle k barn i mengden R til

høyre har samme øyenfarge. Men da har selvfølgelig alle k + 1 barna samme øyenfarge, for barnet helt til venstre og barnet helt til høyre har samme øyenfarge som barna i mellom.

Dermed har vi vist ved induksjon at i en mengde

bestående av n nyfødte barn, har alle samme øyenfarge, uansett hva n er. Derfor har alle nyfødte barn samme øyenfarge.