Tuesday, December 15, 2009

Proof by induction average of rational numbers is a rational number?

Prove by induction on (n is greater than or equal to 1) that the average of n rational numbers is a rational number.





can you please help me set up a formal proof and then prove this?Proof by induction average of rational numbers is a rational number?
Suppose we have a list of n rational numbers:


a_1, a_2, ... , a_n





Let A[k] be the average of the first k elements in the list. Then we have the recursive equation:


A[k] = ( (k-1)*A[k-1] + a_k ) / k


or, by setting k = n:


A[n] = ( (n-1)*A[n-1] + a_n ) / n





The base case is A[1] = a_1 is rational, but this is obvious.





Show


(1) The above recursive equation is correct.


(2) Given A[n-1] is a rational number, it follows that A[n] is a rational number.


- i.e.: Set A[n-1] = s/t and a_n = p/q for some integers s,t,p,q, and actually show that A[n] is fits the same scheme of an integer divided by an integer.

No comments:

Post a Comment