Structural Induction Proof: Induction Step
lTo show ("L) ("A) P(L)
=> P([A | L])
lAssume P(L): ("M) length(append(L, M)) = length(L) + length(M)lTo show P([A | L]):
("M) length(append([A | L], M)) = length([A | L]) + length(M)
lFrom the definition of append, we know that the Òto showÓ part is the same as:
("M) length([A | append(L, M) ]) = length([A | L]) + length(M)
lSince length([A | X]) == 1 + length(X), the Òto showÓ part is equivalent to:
("M) 1 + length(append(L, M)) == 1 + length(L) + length(M)
lBy the induction hypothesis, we can substitute for length(append(L, M)) an expression that renders this as an identity.