Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Induction Proof

  1. Sep 20, 2010 #1
    1. The problem statement, all variables and given/known data

    Prove via Mathematical Induction that, The sum of n rational numbers is rational.

    2. Relevant equations



    3. The attempt at a solution

    Let N = 1
    The sum of one rational number is the number it's self, which is a rational number.

    Assume when n = n, the sum of n numbers is rational

    proof:

    Here's why my problem lies, i don't know what equation this is , or how i would make an equation to sub (n + 1) into ? I'm looking for any guidance that i can get, all help is apreciated..

    Thank's alot,
    -Will
     
  2. jcsd
  3. Sep 20, 2010 #2

    Mark44

    Staff: Mentor

    I would start with n = 2, and show that a/b + c/d is a rational number.
    Assume that when n = k, r1 + r2 + ... + rk is a rational number.
    What is the statement you need to prove when n = k + 1?
     
  4. Sep 20, 2010 #3
    Thank's alot for your help Mark, you really steered me in the right direction here.

    I proved that when n=2 the sum was rational using a/b + c/d etc etc etc, but after i assume that when n=n , for all natural numbers the sum is rational, isn't that as far as you'd think i would have to go? I mean there's no domino effect needed for this proof , just that the sum of n natural numbers is rational, or , do i have to do the n + 1 thing and prove for every n ? but i don't understand how i would go about doing that, :(
     
  5. Sep 20, 2010 #4

    Office_Shredder

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    If you're ever in a situation where n is not equal to n, induction will be the least of your worries.

    It doesn't sound like you completely understand what induction is supposed to be saying. You have to do two things: Prove the statement is true when n=2, which it sounds like you did, and prove that if the statement is true when n=k, it's true when n=k+1

    For example, can you prove that the sum of three rational numbers is rational, using the fact that the sum of two rational numbers is rational? Can you prove that the sum of four rational numbers is rational, using the fact that the sum of three rational numbers is rational? Try to generalize this this for any k
     
  6. Sep 21, 2010 #5

    HallsofIvy

    User Avatar
    Science Advisor

    If you are allowed to use "the sum of two rational numbers is rational" then the problem is easy: If [itex]r_1+ r_2+ r_3+ \cdot\cdot\cdot+ r_k[/itex] is rational, then [itex]r_1+ r_2+ r_3+ \cdot\cdot\cdot+ r_k+ r_{k+1}[/itex][itex]= (r_1+ r_2+ r_3+ \cdot\cdot\cdot+ r_k)+ r_{k+1}[/itex], the sum of two rational numbers.

    Of course, you can prove that the sum of two rational numbers is rational by:
    [tex]\frac{a}{b}+ \frac{c}{d}= \frac{ad+ bc}{bd}[/tex].
     
  7. Sep 22, 2010 #6
    I'm kind of confused by this post.

    Here's my understanding of induction,
    Your proving that it's true for when n = 2, then your assuming it's true for any number n, then you have to prove that if n is true, then n + 1 is true, and so on.

    Your basically proving that it's true for all n > 1 because of the domino effect. I'm still troubled by how to prove n + 1 in this particular proof.

    I did prove that the sum of two rational numbers was rational that exact way, but i don't know how to take it to the next step and prove that n + 1 is rational :(

    So far i've just proven that when n = 2, the sum is rational,

    now i assume when n = k the sum is rational, and have to prove that when n = k + 1 the sum is rational, but i'm completely lost when it comes to doing this for this particular proof.
    :(
     
  8. Sep 22, 2010 #7

    Mark44

    Staff: Mentor

    Part of your confusion might be in the terminology. There's a statement in this and every induction proof, that depends on n in some way. For this problem, it is "The sum of n rational numbers is a rational number."

    It doesn't make a whole lot of sense to talk about the sum of one rational number, so we can assume that n is at least 2. For each value of n >= 2, we get a different statement. E.g,
    S(2): The sum of 2 rational numbers is a rational number.
    S(3): The sum of 3 rational numbers is a rationa number.
    .
    .
    .
    S(k): The sum of k rational numbers is a rational number.
    S(k + 1): The sum of k + 1 rational numbers is a rational number.
    .
    .
    .

    You're not trying to "prove n + 1"; you're trying to prove that the n + 1st statement is true, given that the nth statement is true.



    When n = k, you are assuming that r1 + r2 + ... + rk is a rational number.

    Now, what statement are you trying to prove when n = k + 1, and how can you use your assumption to do this?
     
  9. Sep 23, 2010 #8

    HallsofIvy

    User Avatar
    Science Advisor

    Notice that I said, before, :"if [itex]r_1+ r_2+ r_3+ \cdot\cdot\cdot+ r_k[/itex] is rational, then [itex]r_1+ r_2+ r_3+ \cdot\cdot\cdot+ r_k+ r_{k+1}[/itex][itex]= (r_1+ r_2+ r_3+ \cdot\cdot\cdot+ r_k)+ r_{k+1}[/itex] is the sum of two rational numbers".

    I intentionally used "k" rather than "n" to avoid confusing the "induction step" with the statement in the theorem. But the important point is that since [itex]r_1+ r_2+ r_3+ \cdot\cdot\cdot+ r_k[/itex] is a rational number, then [itex]= (r_1+ r_2+ r_3+ \cdot\cdot\cdot+ r_k)+ r_{k+1}[/itex] is just the sum of two rational numbers, and so rational!
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook