Define the function majority_n as in Problem 9.24. Show that it may be computed with O(n) size circuits.

Problem 9.24.

Recall that you may consider circuits that output strings over {0,1} by designating several output gates. Let add_n : {0,1}²ⁿ → {0,1}ⁿ⁺¹ take two n bit binary integers and produce the n+1 bit sum. Show that you can compute the add_n function with O(n) size circuits.