Question

Help with induction proof
http://prntscr.com/3gyp2j

Answer 1

n = 1 :
\( (a^1 - 1) = (a-1)(a^0) = a-1 \implies 1 \in S\)

Answer 2

I feel stuck after this, help please..

Answer 3

i am familar with induction its just that i was never good at using the 2nd priciple

Answer 4

yeah it looks tough to me as I never did second principle before, here is the assumption :

assume the statement is true for n = 1,2,3,.... k-1 and show that it is trie for n = k

Answer 5

i know for strong induction you need to do 2 base cases

Answer 6

Ahh that makes sense...

n = 2 :
\(a^2 - 1 = (a-1)(a^1 + a^0) = (a-1)(a+1) \implies 2 \in S\) too

Answer 7

so we assume an arbitrary k where its true for k and k+1 and we prove k+2

Answer 8

yes and what about the hint

Answer 9

http://math.stackexchange.com/questions/15371/using-the-second-principle-of-finite-induction-to-prove-an-1-a-1an-1

this link has the exact question and answer

Answer 10

Assumption :
\(a^k - 1 = (a-1)(a^{k-1} + a^{k-2} + ... + a + 1) \)
\(a^{k+1} - 1 = (a-1)(a^{k}+a^{k-1} + ... + a + 1) \)

To prove :
\(a^{k+2} - 1 = (a-1)(a^{k+1} + a^{k} + ... + a + 1) \)

Answer 11

I had a look at MSE earlier, it was incomplete... and i was not able to comprehend it :(

Answer 12

hm.. i try something similar let \[f(n) = a^{n-1} + a^{n-2} + .... + 1\]
so
\[a^k - 1 = (a-1)f(n)\]

Answer 13

oh ok

\(a^{k+1} - 1 = (a-1)f(n+1)\) ?

Answer 14

im not sure how to write it for a^(k+1)
i dont rember the properties on how to pull it out

Answer 15

oh yea thats right haha

Answer 16

so you just need to mani[pulate the a^(k+2) now
\[a^{k+2} - 1 = a(a^{k+1}) - 1\]

Answer 17

yes starting with this we wanto to show it equals \((a-1)f(k+1)\) i guess ?

Answer 18

yea but the thing is im not really too sure on how to manipulate it to look like it

Answer 19

i have difficulty there itself... moving to next step/writing k+2 it in terms of "f(n)"

Answer 20

from the hint

\(a^{n+1} - 1 = (a+1)(a^n-1) - a(a^{n-1}-1)\)

we can cook up :
\[a^{k+2}-1 = (a+1)(a^{k+1}-1) - a(a^k-1)\]

Answer 21

never dealt with functions in proofs before, the notation looks confusing :/

Answer 22

yea im not really sure how that jump works there
im think since

\[a^{k+1} - 1 = (a-1)f(n+1) \]
then
\[1 = a^{k+1} - (a-1)f(n+1)\]
and we subsititute it in the a^(k+2)

Answer 23

\[a^{k+2}-1 = a^{k+2} - \left(a^{k+1} - (a-1)f(n+1)
\right) \]

Answer 24

like this ?

Answer 25

no wait i meant the other 1 on the RHS

Answer 26

\[a^{k+2}-1 = a^{k+2} - \left(a^{k+1} - (a-1)f(n+1) \right) \]

\[a^{k+2}-1 = a^{k+2} - a^{k+1} + (a-1)f(n+1) \]

\[a^{k+2}-1 = a^{k+1}(a - 1) + (a-1)f(n+1) \]

\[a^{k+2}-1 = (a-1)\left(a^{k+1} + f(n+1) \right) \]

Answer 27

i think we're done xD unless im overlooking something...

Answer 28

not done yet im jjust thinking on how to approach this

Answer 29

Only for curiosity, if you assume the hint, maybe you can use it this way,
\[a^{n+1}-1=(a+1)(a^n-1)-a(a^{n-1}-1)=\\
=(a+1)(a-1)(a^{n-1}+\ldots+a+1)-a(a-1)(a^{n-2}+\ldots+a+1)=\\
=(a-1)[(a+1)(a^{n-1}+\ldots+1)-a(a^{n-2}+\ldots+1)]=\\
=(a-1)[a^n+\ldots+a+(a^{n-1}+\ldots+1)-(a^{n-1}+\ldots+a)]=\\
=(a-1)[a^n+\ldots+1]\]

Answer 30

looks simple enough !! looks you have just used "n" and "n-1" to prove "n+1"

Answer 31

Yes, in order to use the hint I apply that.

Answer 32

thank you so much :) I'll give u medal from my other account as you both have helped me nail it down xD

Answer 33

yea john is right on track with that
im completely rusty on the strong induction

Answer 34

the proof is perfect, but i feel John's method is not really a strong induciton as it is not using 1,2,3.... k ?

Answer 35

I'm not sure if it is okay if we just use "n" and "n-1" to prove "n+1"

Answer 36

cuz using just "n" to prove "n+1" is a weak induction... not sure if we can say using "n" and "n-1" is a strong induction

Answer 37

You need to suppose that it is true for k=1,2, and then suppose it is true for n. Then you prove the result for n+1, that is why you use the hint.

Answer 38

Yes thats the first principle proof

Answer 39

Second principle is slightly different :
we suppose 1,2,3...upto k all are true and use it to prove k+1

Answer 40

Yes, it's true.

Answer 41

i think for second principle, in the end we should get :
Because the statement is true for \(n=k+1\), whenever it is true for the integers 1,2,...k, we conclude by the second induction principle that ...

Answer 42

Yes, then I think you can use this solution. I mean, it is true for k=1, k=2, then try for k=n+1. If this is true, the it is done.

Answer 43

thats more like first principle

Answer 44

Following, the Lucas example, it should be like: it is true for k=!, k=2, then assume it is true for k=n and k=n-1. Then for k=n+1 we have the solution.

Answer 45

If it is true for k=n+1, whenever it is true for k=1,2,...,k-1, then for the second induction principle we conclude the result for k=n is also correct.

Answer 46

Makes sense :) the example also used "n" and "n-1" only xD

Answer 47

Something like that :)

Answer 48

thanks a lot John, its very clear now :)

Answer 49

You're welcome. An interesting problem :)!