Handskaningslemmat problemet

Vid induktion är själva idén att ha ett sekvens av påstående, påstående 1, påstående 2, påstående 3... osv, ofta betecknat P(1), P(2), P(3), ..., P(n), ... varav man sedan visar att P(1) (Basfallet) är sannt explicit och sedan visar att om ett av påståendena är sannt så är nästa sannt P(n) -> P(n + 1) (induktionssteget)  och så får man ut att alla påståendena är sanna.

Innan man kan göra det så måste man dock faktiskt formulera vad dessa påståenden är och bestämma vad det är som man "stegar över". I vissa problem är kedjan av påståenden given på förhand men ofta har man en frihet i att välja påståenden.

- P(n) skulle exempelvis kuna vara: Handskakningslemmat, "att summan av nodernas grader är dubbellt så stort som antalet kanter" ($\sum_{v \in V} \text{grad } v = 2E$) gäller för alla grafer med n noder

eller så kunde man ha den alternativa formuleringen

- P(n): Handskakningslemmat, "att summan av nodernas grader är dubbellt så stort som antalet  kanter" ($\sum_{v \in V} \text{grad } v = 2E$) gäller för alla grafer med n kanter.

Båda dessa är vettiga påståenden att jobba med men bevisen blir olika beroende på vilket man väljer. Så välj något av dessa två påståenden och försök.

Om du behöver hjälp med att komma igång med beviset så kan vi ge mer detaljer men jag vill börja med att poängtera att man först måste välja vilka påståenden man jobbar med för att sedan kunna se till basfallet och göra induktionssteget. 

Tack för svar.

Men om vi börjar med denna som du har skrivit

Så vad ska man göra senare? Förlåt för sådana frågor men har inte gjort en liknande fråga tidigare.

- P(n) skulle exempelvis kuna vara: Handskakningslemmat, "att summan av nodernas grader är dubbellt så stort som antalet kanter" (∑v∈Vgrad v=2E) gäller för alla grafer med n noder

Bump.

Intetnet, det står i Pluggakutens regler att man skall vänta åtminstone 24 timmar innan man bumpar sin tråd. 23 timmar är mindra än 24 timmar. Dessutom står det i Pluggakutens regler att man skall visa hur man försöker själv, inte bara sitta och väntar på att någon annan skall lösa ens problem. /moderator