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!

Proof by induction

  1. Mar 4, 2014 #1
    1. The problem statement, all variables and given/known data
    I have two problems that I can't figure out how to turn into summations so I can solve them.

    1. Prove by induction ([itex]\forall[/itex]n)P(n), P(n) is 3|(4[itex]^{n}[/itex]-1)
    I believe the | means divides.

    2. Prove by induction ([itex]\forall[/itex]n)P(n), P(n) is n! [itex]\leq[/itex]n[itex]^{n}[/itex]
     
  2. jcsd
  3. Mar 5, 2014 #2

    maajdl

    User Avatar
    Gold Member

    The symbol "|" probably means "divides" in this context:

    http://en.wikipedia.org/wiki/List_of_mathematical_symbols

    What are the meaning of these "P(n)"?

    There you can read what a proof by induction means:

    http://en.wikipedia.org/wiki/Mathematical_induction

    For example, for problem 1, the first step is to check the statement for some special value of n (typically a small value).
    Take n = 1, for example, and check that 3 divides (4^n-1), which is quite obvious.
    Then try to prove that if the statement is true for any special value n, then it must also be true for the next value n+1 .
    This can be done in two lines of algebra.

    Have fun.
     
  4. Mar 5, 2014 #3

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    Turn into summations? What do you mean with that?
     
  5. Mar 5, 2014 #4
    So that i can solve them with a classic proof by induction where you solve p (1) and show thats true then solve p (k) and p (k+1) using the induction hypothesis. I dontt know how to do this properly without a summstion or how to turn those statements into summations in the form
    $$\sum_{i=1}^{n}i=n$$
    does that ake sense?
     
  6. Mar 5, 2014 #5

    LCKurtz

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    No. Your problem has nothing to do with summations.
     
  7. Mar 5, 2014 #6

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    Perhaps the problem is that you'e only seen induction before when you had to do stuff with summations. But summations are not necessary in order for a proof by induction to work.

    Let's prove (1). You need to prove ##P(n)## holds for all naturals ##n##. If you prove this by induction, then you need to prove two things:

    (a) Prove that ##P(1)## holds.
    (b) Prove that if ##P(k)## holds for some natural ##k##, then ##P(k+1)## holds.

    Can you prove (a) first?
     
  8. Mar 5, 2014 #7
    Hmmm. Ok yes p (1) works, and icanpull out a p (k) and a p (k+1) but everything i know how to do stops there.

    1. P (1) 3|4^1-1=3 and yes 3|3
    $$ p (k)= 3|(4^k-11) $$
    $$ p (k+1)= 3|(4^{k+1}-1) $$
    now what?
     
    Last edited: Mar 5, 2014
  9. Mar 5, 2014 #8
    Ok so
    $$p (k)= 3|(4^k-1)$$
    and i need to get to
    $$ p (k+1)=3|(4^{k+1}-1) $$
    So p (k) is for some m
    $$4^k -1=3m$$
    And p (k+1) is for some p
    $$4^{k+1}-1=3p $$
    Now manipulating p (k) i can add 1 to bothsides and thenmultiply both sides by 4 and then subtract 1
    $$4^{k+1}-1=4(3m+1)-1 $$
    I feel like this is a good direction but i dont know what to do to prove 3|rhs
     
  10. Mar 5, 2014 #9

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    Good. Now prove that ##4(3m + 1) - 1## can be written as ##3a## for some integer ##a##.
     
  11. Mar 5, 2014 #10
    Alright i think i have a solution for both of them now. Thank you all very much for your help
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Proof by induction
  1. Inductive proof (Replies: 9)

  2. Proof by induction (Replies: 2)

  3. Proof by induction (Replies: 32)

  4. Induction Proof (Replies: 14)

  5. Proof by Induction (Replies: 6)

Loading...