Use Proof by Induction for this problem. Please write explanations and show all work. Thanks in advance!

The PairSearch algorithm below takes in an array of ordered pairs data and a value r. It returns a value y such that (r, y) appears in data, or it returns nil if r isn't the first element of an ordered pair. Prove that ProductSearch is correct if data contains a single ordered pair where the first element is x. Hint: if data contains a single ordered pair where the first element is r, then data[i|(x,y) for sone integer i, where y is the correct answer. Also, note that the induction hypothesis for this problem will only apply to arravs that contain one pair that starts with r Input: data: an array of ordered pairs Input: n: the number of ordered pairs in data Input: r: a value to search for Output: value y such that (x. y) E data, or nil if no such pair exists Algorithm: PairSearch 2 if n 0 then 3return nil 4 else if data 1.first- then 5 return data 1l.second 6 else 7f data 1] first T'S Iterate through data and remove all ordered pairs (a, b) where (a )f -a) >0 return PairSearch(data, ar) x) > 0 10 end