1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Two Simple Induction Proofs

  1. Jan 21, 2008 #1
    1. The problem statement, all variables and given/known data
    Prove 1^3 + 2^3 + ... + n^3 = (1 + 2 + ... + n)^2 for all natural numbers n.


    2. Relevant equations



    3. The attempt at a solution

    Well, this seems like the typical induction proof, so I start by testing the hypothesis at 1: 1^3 = 1^2 = 1. Then I assume that the equation is true for n, and try to prove it true for n + 1.

    1 ^3 + 2^3 + ... + n^3 + (n + 1)^3 = (1 + 2 + ... + n)^2 + (n + 1)^3

    I have this, but how do I get it to be (1 + 2 + ... + n + n + 1)^2? Is it some crazy factorization that I'm overlooking? It seems pretty easy.


    1. The problem statement, all variables and given/known data

    Prove that 7^n - 6n - 1 is divisible by 36 for all positive integers n.

    2. Relevant equations



    3. The attempt at a solution

    Well, the statement seems to be saying the following: 7^n - 6n - 1 = 36k, where k is a positive integer. As with the first problem, testing it with 1 works. Assuming it is true for n + 1 would mean the following, if I'm correct:

    7^(n + 1) - 6(n + 1) - 1 = 36j, where j is a positive integer. At this point, I'm not sure how to proceed.


    I know I'm probably overlooking some obvious stuff here, so a little hint is probably all I'll need to finish these problems off. Thanks! :)
     
  2. jcsd
  3. Jan 21, 2008 #2
    Try to substitute something else for (1+2+...+n). The formula for it is not that hard to derive.
    7^(n+1) = 7^n*7. You are assuming that 7^n = 36k + 6n + 1. See what happens.
     
  4. Jan 21, 2008 #3

    rock.freak667

    User Avatar
    Homework Helper

    [tex]1^3 + 2^3 + ... + n^3=\sum_{n=0} ^{N} n^3[/tex]

    [tex](1 + 2 + ... + n)^2 =(\sum_{n=0} ^{N} n)^2[/tex]


    Do you know what [itex] \sum_{n=0} ^{N} n[/itex] represents?
     
  5. Jan 22, 2008 #4
    Thanks guys for your help! I solved the second problem. The first problem is still puzzling me a bit. Here's what I have:

    [tex]1^3 + 2^3 + ... + n^3 = \sum_{n=0} ^{N} n)^2 + (n + 1)^3[/tex]

    Still not sure how to add those two terms together. I'm sure it's very easy, but I'm just not seeing it.
     
  6. Jan 22, 2008 #5

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    The same question, again, can you write
    [itex]\sum_{n=0}^N n[/itex]
    in a "closed" form and then square?
     
  7. Jan 22, 2008 #6
    Got it! Thank you. :)
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Two Simple Induction Proofs
  1. Simple Induction Proof (Replies: 2)

Loading...