Recall from linear algebra that a vector in Rn is an ordered n-tuple of real numbers. We can easily implement vectors as lists. The ith component of the vector will be stored as the ith element of the list.
The dot product between two vectors V = (v1, v2,...vn) and W = (w1, w2,...wn) is given by
For example,
(1, 2, 3)
(4, 5, 6) = (1 * 4) + (2 * 5) + (3 * 6) = 32
The following Scheme function takes two vectors (represented as lists) and returns the dot product of the vectors (assuming they're of the same length.)
(define dot-product
(lambda (v w)
(if (and (empty? v) (empty? w))
0
(+ (* (head v) (head w))
(dot-product (tail v) (tail w)))))
Using the informal version of the substitution model, prove by induction that, for any vectors u and v of the same size,
(dot-product u v) = uv
Don't forget to write down all of the necessary ingredients of an induction proof: the variable you're inducting over, the property you're trying to prove, the base case, a clear statement of your inductive hypothesis, and finally a proof of the inductive case.