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

  • Thread starter tonit
  • Start date
  • #1
55
1

Homework Statement


Prove that there are 3^n n-digit numbers formed with the numbers 4, 5, 6.
The digits can be repeated, e.g.: 444.


Homework Equations


-


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
 

Answers and Replies

  • #2
I like Serena
Homework Helper
6,577
176

Homework Statement


Prove that there are 3^n n-digit numbers formed with the numbers 4, 5, 6.
The digits can be repeated, e.g.: 444.


Homework Equations


-


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
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?
 
  • #3
55
1
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. ?
 
  • #4
I like Serena
Homework Helper
6,577
176
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.
 
  • #5
55
1
ok thanks :D
 

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

Replies
2
Views
1K
Replies
18
Views
9K
Replies
17
Views
8K
Replies
5
Views
990
Replies
18
Views
1K
Replies
12
Views
2K
  • Last Post
Replies
3
Views
4K
  • Last Post
Replies
11
Views
2K
Top