1. Limited time only! Sign up for a free 30min personal 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!

Proof by Induction and divisibility

  1. Mar 23, 2004 #1
    How would I go about proving that 8^n - 3^n (n >= 1) is divisible by 5 using mathematical induction? I tried this but I do not think it is right:

    First, prove that 8^1 - 3^1 is divisible by 5. 8^1 - 3^1 = 5, which is divisible by 5.

    Second, prove that 8^(k+1) - 3^(k+1) is divisible by 5 if k = n. Notice that 8^(k+1) - 3^(k+1) =

    8*(8^k) - 3^k(3). Based on the induction hypothesis, we already know that 8^k - 3^k is divisible by 5. So we end up with 24*(8^k - 3^k), which is always divisible by 5 because the term inside the parenthesis is already divisible by 5. Multiplying that by any number will not change the fact that it is divisible by 5.

    Am I right here? Thanks.
     
  2. jcsd
  3. Mar 23, 2004 #2
    How did you figure this:
    [tex]8*8^k - 3*3^k = 24(8^k - 3^k)[/tex]
    ?? You were doing fine up until that point. What you need to do is this:
    [tex]8*8^k - 3*3^k = 5*8^k + 3*8^k + 3*3^k = 5*8^k + 3(8^k - 3^k)[/tex]
     
  4. Mar 23, 2004 #3
    OK, I'm having trouble with this one as well. Can someone help me?

    1^2 + 3^2 + 5^2 + ... + (2n - 1)^2 = (n(2n - 1)(2n + 1))/3
     
  5. Mar 24, 2004 #4
    [tex]1^2 + 3^2 + 5^2 + ... + (2n - 1)^2 = \frac{n(2n - 1)(2n + 1)}{3} = \frac{4n^3 - n}{3}[/tex]

    So for [tex]k = n + 1[/tex]:
    [tex]1^2 + 3^2 + 5^2 + ... + (2n - 1)^2 + (2n + 1)^2 = \frac{(n + 1)(2n + 1)(2n + 3)}{3}[/tex]
    [tex]\underline{1^2 + 3^2 + 5^2 + ... + (2n - 1)^2} + (2n + 1)^2 = \frac{4n^3 + 12n^2 + 11n + 3}{3}[/tex]
    We already know it's true for [tex]n[/tex] so you can replace the underlined part:
    [tex]\frac{4n^3 - n}{3} + (2n + 1)^2 = \frac{4n^3 - n}{3} + 4n^2 + 4n + 1 = \frac{4n^3 + 12n^2 + 11n + 3}{3}[/tex]
    Multiply by 3:
    [tex]4n^3 - n + 12n^2 + 12n + 3 = 4n^3 + 12n^2 + 11n + 3[/tex]
    QED.
     
  6. Mar 24, 2004 #5
    I have seen a beautiful geometrical way of deriving the sum of cubes of numbers, i.e. 1^3 + 2^3 + ... + n^3 = (1+2+...n)^2.

    I wonder if there are simple ways of deriving [tex]1^2 + 3^2 + 5^2 + ... + (2n - 1)^2 = \frac{n(2n - 1)(2n + 1)}{3}[/tex]
     
  7. Mar 24, 2004 #6
    You can prove this:
    [tex]1^2 + 3^2 + 5^2 + ... + (2n - 1)^2 = \frac{n(2n - 1)(2n + 1)}{3}[/tex]
    With a bit of geometry, yes. If you draw squares with a side of 1, 3, 5, etc., one below the other, you can find the sum of their areas with a bit of manipulation, but it's not exactly simple (the idea is simple, the equations are a bit big though).
     
  8. Oct 14, 2004 #7
    I have a problem:
    Knowing that [tex]1^2 + 2^2 + 3^2 + ... + n^2 = \frac{n(n + 1)(2n + 1)}{6}[/tex]and that [tex]1^3 + 2^3 + 3^3 + ... + n^3 = \frac{n^2 (n + 1)^2 } {4}[/tex], calculate [tex]1^4 + 2^4 + 3^4 + ... + n^4[/tex].
    Please, help me!
     
    Last edited: Oct 14, 2004
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Proof by Induction and divisibility
  1. Proof by induction (Replies: 0)

  2. Proof by Induction (Replies: 9)

  3. Induction Proof (Replies: 5)

  4. Induction Proof (Replies: 1)

  5. Induction proof (Replies: 2)

Loading...