Induktionsbevis

Andra raden i ditt bevis stämmer inte.

Aah ok det ser jag också nu. Hade man kunnat säga (mod k) ist och föra ett liknande resonemang?

Jag vet inte. Jag kommer inte ens ihåg hur man brukar bevisa den här saken, men det borde gå att hitta ett bevis med induktion.

Är det en uppgift i någon lärobok? Eller någon hypotes du själv kommit på?

beerger skrev:

Är det en uppgift i någon lärobok? Eller någon hypotes du själv kommit på?

Nej det är något jag själv var nyfiken på om jag kunde bevisa. Bevisligen kunde jag inte det.

Laguna skrev:

Jag vet inte. Jag kommer inte ens ihåg hur man brukar bevisa den här saken, men det borde gå att hitta ett bevis med induktion.

Ok men om jag istället för att bevisa delbarhet med k!, kan jag visa delbarhet med k. Då bör det väl vara så att:

x + 1 = x + 1 (mod k)

x + k + 1 = x + 1 (mod k)

och då kan jag använda IH och bevisar på så sätt att produkten av k på varandra följande icke-negativa heltal är delbar med k?

Det jag menar är följande bevis:

P(a): "(a+1)(a+2)...(a+k) delas av k",  a ≥ 0

Basfall P(0): "(0+1)(0+2)...(0+k) delas av k"

(0+1)(0+2)...(0+k) = k! som delas av k

Stegfall P(b) ==> P(b+1)

Anta att P(b): "(b+1)(b+2)...(b+k) delas av k",  b ≥ 0

Visa att P(b+1): "(b+2)(b+3)...(b+k+1) delas av k"

Bevis:

b + 1 = b + 1 (mod k)

b + k + 1 = b + 1 (mod k)

Det ger:

(b+2)(b+3)...(b+k+1) = (b+2)(b+3)...(b+k)(b+1)   (mod k)

                                        = 0 (mod k)                              (IH)

Vilket skulle visas.

Vad säger ni om det? Med det här beviset, om det håller, kan man visa det jag först ville visa, tänker jag.    

Att produkten är delbar med k har du visat så, ja. Men hur kommer man till att den är delbar med k fakultet?

Laguna skrev:

Att produkten är delbar med k har du visat så, ja. Men hur kommer man till att den är delbar med k fakultet?

Om du har en produkt av k på varandra följande tal, finns i den produkten två andra produkter av k - 1 på varandra följande tal, som då ska delas av k - 1. Om vi fortsätter med samma resonemang, når vi till slut att det finns k tal i produkten som delas av 1. Sammanfattat:

Produkten av k på varandra följande tal delas av k(k-1)(k-2)...1 = k!

Bara en idé. Har inte tänkt igenom det helt än.

Så här tänker jag varför det måste vara sant:

Låt säga att det är falskt, att om k, (k-1) ... , 2, 1 delar produkten av k på varandra följande tal, implicerar det inte att k! delar den. Då ska det finnas två tal, a och b, 1 < a < b ≤ k, sådana att när vi delar med det ena talet, kan vi inte längre dela med det andra. Låt a och b vara de minsta sådana talen vi kan hitta.

Fall 1. gcd(a, b) = 1

Trivialt falskt. Om de inte har gemensamma delare, försvinner inga av a:s delare då vi delar med b och vice versa.

Fall 2. gcd(a, b) > 1

Låt gcd(a, b) = c och definiera a och b i termer av c:

a = pc

b = qc

Om vi delar med b, ska vi inte längre kunna dela med a. Det betyder att c förekommer exakt en gång i produkten:

(x+1)(x+2)...(x+k) = p*q*c*A,   där A är något tal.

Delar vi med b får vi:

(x+1)(x+2)...(x+k)/b = p*A, vilket inte längre är delbart med a

Eftersom b = q*c > a > 1, är q och c större än ett. Då gäller även att q < b, och eftersom produkten inte längre är delbar med q, motsäger det påståendet att a och b var de minsta talen vi kunde hitta, för vilka detta skulle gälla. Alltså måste k! dela en produkt av k på varandra följande tal.

Kan man anta att om det inte uppstår problem efter 2 tal kommer det inte göra det senare heller?

Tex 32 går att dela med 2 av talen 8, 4 och 2, men inte med alla 3 samtidigt.

Micimacko skrev:

Kan man anta att om det inte uppstår problem efter 2 tal kommer det inte göra det senare heller?

Tex 32 går att dela med 2 av talen 8, 4 och 2, men inte med alla 3 samtidigt.

Nej, kanske inte. Har du några förslag på vad man kan göra istället?

Jag antar att du har rätt, men jag är inte helt övertygad om liknelsen. 32 är ett tal i en produkt av 8 på varandra följande tal. Jag är inte helt övertygad om att det skulle göra någon skillnad heller, å andra sidan ... 

Micimacko skrev:

Kan man anta att om det inte uppstår problem efter 2 tal kommer det inte göra det senare heller?

Tex 32 går att dela med 2 av talen 8, 4 och 2, men inte med alla 3 samtidigt.

Men såhär då:  a och b var de minsta talen vi kunde hitta för vilka det är skulle gälla, men så visar det sig att det finns ett tredje tal c, sådant att när vi delar med några två tal före det tredje, kan produkten inte längre delas av det tredje. Då kan vi definiera a' = ab, ac eller bc och b' = den som blir över. T.ex a' = ab, b' = c. Då är gcd(a', b') = c' och vi kan köra samma resonemang igen. Om vi fortsätter att skapa nya tal a', kommer a' till slut vara större än k, vilket också är en motsägelse.

Jag ville bara visa att det kan dyka upp nya saker senare än delning nr 2, men ditt antagande är jag nästan säker på att det är sant. Jag kan se det i huvudet genom att tänka mod k, mod k-1 osv men jag skulle inte kunna få ner det i text tyvärr.

Vet vi att de nyskapade talen inte blir större än k?

Tillägg: 17 okt 2021 22:34

Jag läste visst inte klart. Ska fundera på det.

Micimacko skrev:

Vet vi att de nyskapade talen inte blir större än k?

Om jag fortsätter att skapa nya tal a' genom att plocka tal ur mängden (1, k] och multiplicera ihop dem, måste a' snart vara större än k. Om jag väljer alla utom k t.ex blir a' = (k-1)! som definitivt är större än k för k > 2.