Consider the following Python function foo, which takes as input an integer n21 and returns a tuple of length 2 of integers: def foo(n): assert n>=1 if n 1: return (1, 2) else: p, a foo(n-1) return (q + p*n* (n+1), q*n* (n+1)) Prove that for n21, foo(n) (p, q) such that 1 1 9 n+1 (Hint: induction on n.)