Latex Help need. Write Latex Code please. Im using overleaf. Thanks . Problem from chapter 0 book : Introduction to the Theory of Computation

S(n) = 12 +22+...+n Show that S(n) = 1 (213 + 3n2 +n), n> 1 Proof by induction (completc). Base case: n = 1 lhs = S(1) = 12 = 1 rhs = (2- 13 +3.12 +1) = So lhs = rhs and true for n=1 Inductive case: Assume true for n=k, k > 1: S(K) = (23 +3k + k) Show true for n=k+1: lhs = S(k+1) = 12 + 22 + ... + (k + 1)2 = (12 +22+...+k) + (k+1) This = 2(2k +1) + 3(k + 1)2 + (k + 1)) So lhs = rhs and truc for n=k+1