Proof by Induction: Solving Homework Equations

[roam]

Homework Statement

http://img200.imageshack.us/img200/7097/99175506.gif

Homework Equations

The Attempt at a Solution

For $$n \in N$$ let P(n) be the statement: "81 | (10ⁿ⁺¹-9n-10)"

Base Case: when n=1: 10ⁿ⁺¹-9n-10 = 81 = 81 × 1

So P(1) is true

Inductive Step: let $$k \in N$$ and suppose $$P(k)$$ is true, that is 81 | (10^k+1-9k-10) is true. Then $$10^{k+1}-9k-10=81m$$ for some $$m \in Z$$. Then $$10^{k+1}=(81m+9k+10)$$.

So,

10^k+2-10(k+1)-10=10 × 10^k+1-10(k+1)-10

=10 × (81m+9k+10)-10k+10-10

= 10 × (81m+9k+10-k)

I'm stuck here and I don't know how to factor things out and bring the 81 forth to get the expression in the form: "81(something here)" to show that it's divisible by 81 for all n. Any help is appreciated.

P.S.
I might be able to do it this way:

10 × (81m+9k+10-k) = 810m+90k+100-10k
=> 81(10m+(90/81)k+(100/81)-(10/81)k)

But I don't feel that this is the right way...

 

[rock.freak667]

P.S.
I might be able to do it this way:

10 × (81m+9k+10-k) = 810m+90k+100-10k
=> 81(10m+(90/81)k+(100/81)-(10/81)k)

But I don't feel that this is the right way...

That is how you'd arrive at your answer.

 

[roam]

That is how you'd arrive at your answer.

It's a bit awkward... are you sure that there is not a better way?

 

[snipez90]

You have a few typos in your inductive step (should be 9(k+1), not 10(k+1)).

Note that
$$10^{(k+1)+1} - 9(k+1) - 10 = 10\cdot10^{k+1} - 9k - 9 - 10 = 10(10^{n+1} - 9n - 10) + 81n + 81$$

 

[roam]

How did you get from $$10\cdot10^{k+1} - 9k - 9 - 10$$ to $$10(10^{n+1} - 9n - 10) + 81n + 81$$? Could you please explain :)

Yes that was a typo but I thought it would be a good way to replace 10^k+1 by 81m+9k-10, since $$10^{k+1}-9k-10=81m \Rightarrow 10^{k+1} = 81m+9k+10$$

 

[mathie.girl]

Homework Statement

http://img200.imageshack.us/img200/7097/99175506.gif
Inductive Step: let $$k \in N$$ and suppose $$P(k)$$ is true, that is 81 | (10^k+1-9k-10) is true. Then $$10^{k+1}-9k-10=81m$$ for some $$m \in Z$$. Then $$10^{k+1}=(81m+9k+10)$$.

So,

10^k+2-10(k+1)-10=10 × 10^k+1-10(k+1)-10

=10 × (81m+9k+10)-10k+10-10

= 10 × (81m+9k+10-k)

I'm stuck here and I don't know how to factor things out and bring the 81 forth to get the expression in the form: "81(something here)" to show that it's divisible by 81 for all n. Any help is appreciated.

The above looks good, without some typos. Should be:
10^k+2-9(k+1)-10=10 × 10^k+1-9(k+1)-10
=10(81m+9k+10)-9k-9-10

Then keep going.

 

[snipez90]

How did you get from $$10\cdot10^{k+1} - 9k - 9 - 10$$ to $$10(10^{n+1} - 9n - 10) + 81n + 81$$? Could you please explain :)

You always want to apply the inductive hypothesis as easily as possible. If the inductive step gives you
$$10^{(k+1)+1} - 9(k+1) - 10 = 10\cdot10^{(k+1)} - 9(k+1) - 10 ,$$
then the fact that you can pull out the very first 10 factor on the right hand side suggests multiplying the expression $$10^{(k+1)} - 9k - 10$$ in our inductive hypothesis by 10 and relating it to the inductive step somehow.

 

[rock.freak667]

$$H_N: 10^{N+1}-9N-10=81m$$

x10

$$10^{N+2}-90N-100=810m$$

$$10^{N+2}-90N-90-10=810m$$

$$10^{N+2}-90(N+1)-10=810m \Rightarrow 10^{N+2}-9(N+1)-10=810m+81(N+1)$$

Left side happens to be H_N+1 and the right side is divisible by 81 no matter what N is...

so even if it is awkward, once you show it is divisible by 81, you have proven it.