Really Simple Induction qn... (1 Viewer)

Kostie100 · Oct 17, 2012

Prove using mathematical induction, (8ⁿ - 1) is divisible by 7.

Jashua_Long · Oct 17, 2012

Prove true n=1 (trivial).

Assume true n=k

8^k - 1 = 7M

Prove true n=k+1

i.e. RTP

8^(k+1) - 1 = 7C

LHS = 8*8^k - 1
= 8 [ 7M +1 ] - 1 [ from assump]
= 8*7M +7
= 7[ 8M +1]
= 7C

Sy123 · Oct 17, 2012

$$Let the expression $ 8^n-1=7p \ \ \ p-integer$

$Step 1: $n=1 \\ 8^1-1=7=7p \ \ \rightarrow p=1 \ \therefore p-integer \\ \\ \therefore $ It is divisible at n=1$

$Step 2: $n=k \\ 8^k-1=7p \ \ p-integer \ \ \ $Assume true for n=k$

$Step 3: $n=k+1 \\ \\ 8^{k+1}-1=7q \ \ q-integer \ \ \rightarrow $to prove$

$8^{k+1}-1=8 \cdot 8^k-1=7 \cdot 8^k+8^k-1 \\ \\ $Using step 2$ \ \ 8^{k+1}-1=7\cdot 8^k+7p=7(8^k+p) \ \\ \\ \ 8^k $ is an integer and p is integer, hence the whole expression must be an integer$ \\ \\ \therefore 7(8^k+p)=7q \ \ \ q-integer$

$\therefore $The RHS of Step 3 is true$$

$\therefore $The statement is true for n=1$ \\ $If the statement true for n=k, it must be true for n=k+1$ \\ $Hence the statement must be true for all n positive integral$$

Leffife · Oct 17, 2012

Base Step:
Test true for n = 1
i.e. 8¹ - 1 = 7 (7 is divisible by 7, thus true)

Now, assume the function is true for n = k
i.e. (8^k) - 1 = 7k (k is just some integer)

Prove:
8(8^k) - 1
= 8(7k + 1) - 1 ........... from assumed before (look up) I rearranged (8^k) - 1 = 7k into 7k + 1 = 8^k
= 8(7k) + 8 - 1
= 8(7k) + 7
= 7(8k + 1)
= 7L for some integer L

So we got 8^(k + 1) - 1 = 7L, where we can state that the statement is divisible by 7.

Leffife · Oct 17, 2012

Base Step:
Test true for n = 1
i.e. 8¹ - 1 = 7 (7 is divisible by 7, thus true)

Now, assume the function is true for n = k
i.e. (8^k) - 1 = 7k (k is just some integer)

Prove:
8(8^k) - 1
= 8(7k + 1) - 1 ........... from assumed before (look up) I rearranged (8^k) - 1 = 7k into 7k + 1 = 8^k
= 8(7k) + 8 - 1
= 8(7k) + 7
= 7(8k + 1)
= 7L for some integer L

So we got 8^(k + 1) - 1 = 7L, where we can state that the statement is divisible by 7.

Jashua_Long · Oct 17, 2012

Leffife said:
Base Step:
Test true for n = 1
i.e. 8¹ - 1 = 7 (7 is divisible by 7, thus true)

Now, assume the function is true for n = k
i.e. (8^k) - 1 = 7k (k is just some integer)

Prove:
8(8^k) - 1
= 8(7k + 1) - 1 ........... from assumed before (look up) I rearranged (8^k) - 1 = 7k into 7k + 1 = 8^k
= 8(7k) + 8 - 1
= 8(7k) + 7
= 7(8k + 1)
= 7L for some integer L

So we got 8^(k + 1) - 1 = 7L, where we can state that the statement is divisible by 7.

Souldn't use k twice, it makes things very confusing. I always use M or P, letters that don't come up elsewhere.

Kostie100 · Oct 18, 2012

Wow thanks everyone for the reasoning, i understand it now.

Really Simple Induction qn... (1 Viewer)

Kostie100

Member

Jashua_Long

Banned

Sy123

This too shall pass

Leffife

A lover is a best friend