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

1. Apr 7, 2012

### tonit

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 $P$(1) is true, because we have only 4, 5, 6.

But it seems to me unreasonable to say $P$(k)$=> P$(k+1)

any help is appreciated

2. Apr 7, 2012

### I like Serena

Hi tonit!

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. Apr 7, 2012

### tonit

that would be $3^k * 3 = 3$k+1

so is all this enough, or does the problem need other explanations. ?

4. Apr 7, 2012

### I like Serena

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. Apr 7, 2012

ok thanks :D