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!

Homework Help: 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


    User Avatar
    Gold Member

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


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

    There you can read what a proof by induction means:


    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
    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
    does that ake sense?
  6. Mar 5, 2014 #5


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    No. Your problem has nothing to do with summations.
  7. Mar 5, 2014 #6
    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
    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
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted