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!

Prove that there are 3^n n-digit numbers formed with 4, 5 ,6

  1. Apr 7, 2012 #1
    1. The problem statement, all variables and given/known data
    Prove that there are 3^n n-digit numbers formed with the numbers 4, 5, 6.
    The digits can be repeated, e.g.: 444.


    2. Relevant equations
    -


    3. The attempt at a solution
    What I thought was to prove it by induction. So [itex]P[/itex](1) is true, because we have only 4, 5, 6.

    But it seems to me unreasonable to say [itex]P[/itex](k)[itex] => P[/itex](k+1)

    any help is appreciated
     
  2. jcsd
  3. Apr 7, 2012 #2

    I like Serena

    User Avatar
    Homework Helper

    Hi tonit! :smile:

    So suppose there are ##3^k## numbers with k digits.
    The numbers with (k+1) digits would be one digit longer.
    That is, they would have one more digit to the left.

    How many numbers of (k+1) digits could you make, given that the last k digits are fixed?
     
  4. Apr 7, 2012 #3
    that would be [itex]3^k * 3 = 3[/itex]k+1
    thanks btw for the reply.

    so is all this enough, or does the problem need other explanations. ?
     
  5. Apr 7, 2012 #4

    I like Serena

    User Avatar
    Homework Helper

    A proof by full induction involves 2 steps.

    The boundary condition that ##P_{(1)}## is true.

    The induction hypothesis that ##P_{(k)}## is true, followed by the proof that it implies that ##P_{(k+1)}## is true as well.

    You just showed both.
    So yes, that is enough.
     
  6. Apr 7, 2012 #5
    ok thanks :D
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Prove that there are 3^n n-digit numbers formed with 4, 5 ,6
  1. Solve n^5+80=5n^4+16n (Replies: 11)

Loading...