Question

Proof of a^n - 1

Answer 1

I am supposed to prove the problem a^n - 1 by induction.

The problem reads, "Use the second principle of finite induction to establish that
\[a^n-1=(a+1)(a^{n-1}+a^{n-2}+...+a+1)\] for all n >= 1

I have no idea how to go about solving this problem. I'm not looking for an answer, just a push in the right direction.

Answer 2

hmmm... your identity does not look correct to me

Answer 3

for n=1 you get:\[a^1-1=(a+1)(1)\]\[a-1=a+1\]which is not correct

Answer 4

Oh, oops. (a-1)(a^(n-1)+a^(n-2)+...+a+1)

Answer 5

that looks better :)

Answer 6

do you know how to perform a proof by induction?

Answer 7

Yes, but I haven't done any where you assum 1,2,...k-1 are true.

Just ones where if 1 is true and when k is true k+1 is true

Answer 8

assume*

Answer 9

there is only one kind that I am aware of:

1. Prove that the statement is true for the starting value of n (in this case n=1)
2. Assume the statement is true for some n=k
3. Use this to prove that it must also be true for n=k+1

Answer 10

Ah. Well the book I'm reading from says that sometimes you may need to assume all values between 1 and k are true before you show k+1 is true. Like with recursive functions.

Answer 11

think about how you are proving this and what induction means.

1. You show the statement is true for n=1 - which we can do easily in this case
2. You assume the statement is true for n=k
3. You then shown that this implies it must also be true for n=k+1

Then, using induction, since you showed it was true for n=1, then it must also be true for n=2 (from steps 2 and 3 above).
If its true for n=2, then it must also be true for n=3 (again using steps 2 and 3)
etc.

Answer 12

Yeah, I understand that. I'm just not sure how to move from assuming it is true for to showing that it implies it is true for k+1 in this problem

Answer 13

give it a go and show your steps - I will try and guide you if you get stuck anywhere

Answer 14

The problems I have worked are things like 1 + 3 + 5 + ... + (2n - 1) = n^2 which I don't have any problems with, because I can add 2((k+1)-2) to both sides and solve it, but I don't know what to do with k+1 here.

I have no idea where to go once I've put a^k - 1 = (a - 1)(a^(k-1)+...+a+1)

Answer 15

OK, lets start with what we are trying to prove::\[a^n-1=(a-1)(a^{n-1}+a^{n-2}+...+a^0)\]Step 1:
For n=1, we get:\[a^1-1=(a-1)(a^0)\]\[\therefore a-1=a-1\]which is correct. So we have proved it is true for n=1

Step 2:
Assume it is true for n=k, so we have:\[a^k-1=(a-1)(a^{k-1}+a^{k-2}+...+a^0)\]

Answer 16

Step 3:
Now we try and show that this implies it is also true for n=k+1.
So, for n=k+1 we get:\[a^{k+1}-1=a\times a^k-1\]Can you see what to do next?

Answer 17

Replace \(a^k\) here with the expression we assumed was true in step 2 above

Answer 18

\[(a-1)(a^{k-1}+a^{k-2}+...+a+1)+1?\]

Answer 19

yes that is the correct expression for \(a^k\)

Answer 20

Use this to replace \(a^k\) in:\[a\times a^k-1\]

Answer 21

I assume you are working it out?

Answer 22

Yeah, sorry. I was working it on paper.

Wouldn't the +1 cause a problem though?

\[a*a^k - 1 =a[(a-1)(a^{k-1}+a^{k-2}+...+a+1)+1] - 1\]

Answer 23

suggestion:
\[\large a^{k+1}-1=a^{k+1}-a+a-1=(a^{k+1}-a)+(a-1)=a(a^k-1)+(a-1)\]

Answer 24

not it won't - just move the 'a' inside the brackets - you will soon see how this simplifies