Dokaz

TRDITEV: Oba seznama hkrati ne moreta biti prazna.

BAZA: Dokazati moramo, da je trditev veljavna za vsako dolžino prvega niza, ki je večja od 0 in drugega, ki je 0, ter obratno.

1.

$sez1 = NULL, sez2 {\neq} NULL;$
Ker je sez1 prazen seznam, vrnemo sez2.
Iz tega sledi, da je trditev veljavna.

2.

$sez1 {\neq} NULL, sez2 = NULL ;$
Ker je sez2 prazen sezanam, vrnemo sez1.
Iz tega sledi, da je trditev veljavna.

PREDPOSTAVKA: Predpostavljamo, da je trditev veljavna za vsako dolžino prvega seznama, ki je največ n₁ in drugega, ki je največ n₂.

|sez1| = n₁
|sez2| = n₂

KORAK: Dokazati moramo, da je trditev veljavna:

• za vsako dolžino prvega niza, ki je največ n₁ + 1 in drugega, ki je največ n₂
• za vsako dolžino prvega niza, ki je največ n₁ in drugega, ki je največ n₂ + 1
• za vsako dolžino prvega niza, ki je največ n₁ + 1 in drugega, ki je največ n₂ + 1

1.

|sez1| = n₁ + 1
|sez2| = n₂
Ker noben od seznamov ni prazen, se sprehodimo po zanki do - while.

• Če je vred_glave(sez1) > vred_glave(sez2), se izloči glava iz sez2, dolžina sez2 pa se zmanjša za 1. Torej je
  
  |sez2| = n₂ - 1, |sez1| = n₁ + 1
  
  
  Dolžina sez2 se zmanjšuje za 1 toliko časa
  • dokler sez2 ni prazen
    Za ta primer pa smo že dokazali veljavnost trditve (baza).
  • ali pa dokler vred_glave(sez1) ni manjša od vred_glave(sez2)
    V tem primeru se izloči glava iz sez1, dolžina sez1 pa se zmanjša za 1. Sledi, da je
    
    $$\vert sez1\vert = n_{1}, \\ \vert sez2\vert = n_{2} - 1$$
    
    
    Ker pa je po predpostavki, trditev veljavna za vsako |sez1| = n₁ in |sez2| = n₂, potem velja tudi za ta primer, ko sta niza dolga n₁ in n₂ - 1.

• Če pa je vred_glave(sez1) < vred_glave(sez2), potem se izloči glava iz sez1, dolžina sez1 pa se zmanjša za 1. Torej je
  
  |sez1| = n₁, |sez2| = n₂
  
  
  Po predpostavki, pa trditev velja za ta dva niza.

2.

|sez1| = n₁
|sez2| = n₂ + 1
Ker noben od seznamov ni prazen, se sprehodimo po zanki do - while.

• Če je vred_glave(sez1) > vred_glave(sez2), se izloči glava iz sez2, dolžina sez2 se zmanjša za 1. Torej je
  
  |sez2| = n₂, |sez1| = n₁
  
  
  Po predpostavki pa trditev velja za ta dva niza.
• Če pa je vred_glave(sez1) < vred_glave(sez2), potem se izloči glava iz sez1, dolžina sez1 pa se zmanjša za 1. Torej je
  
  |sez1| = n₁ - 1, |sez2| = n₂ + 1
  
  
  Dolžina sez1 se zmanjšuje za 1 toliko časa
  • dokler sez1 ni prazen
    Za ta primer pa smo že dokazali,da trditev velja (baza).
  • ali pa dokler vred_glave(sez1) ni večja od vred_glave(sez2)
    V tem primeru se izloči glava iz sez2, dolžina sez2 pa se zmanjša za 1. Sledi, da je
    
    |sez2| = n₂, |sez1| = n₁ - 1
    
    
    Po predpostavki pa je trditev veljavna, za vsako dolžino sez1, ki je največ n₁ in dolžino sez2, ki je največ n₂. Torej velja tudi za primer, ko je
    
    $$\vert sez2\vert = n_{2}, \\ \vert sez1\vert = n_{1} - 1$$
    
    

3.

|sez1| = n₁ + 1
|sez2| = n₂ + 1
Ker noben od seznamov ni prazen se sprehodimo po zanki do - while.

• Če je vred_glave(sez1) > vred_glave(sez2), se izloči glava iz sez2, dolžina sez2 se zmanjša za 1. Torej je
  
  |sez2| = n₂, |sez1| = n₁ + 1
  
  
  Pravilnost trditve za ta primer pa smo že pokazali v točki 1.

• drugače pa se izloči glava iz sez1, dolžina sez1 pa se zmanjša za 1. Sledi, da je
  
  |sez1| = n₁, |sez2| = n₂ + 1
  
  
  Za ta primer pa smo pokazali veljavnost trditve v točki 2.