Induction question (1 Viewer)

[YBK]

Hey just an induction question, I actually proved it but just to make sure that my method is right.. the cambridge doesn't have solutions to them and we still haven't learnt this topic in class...


Show that 7^n + 11^n is divisible by 9 for odd n>=1

for n = 1
7 + 11 = 18, which is divisible by 9


7^n + 11^n = 9m

Now suppose that n=k
7^k + 11^k = 9m ........... (1)

Suppose that n = k+2
7^k+2 + 11^k+2
= 7^k * 7^2 + 11^k * 11^2
= (9m - 11^k) * 7^2 + (9m - 7^k) * 11^2 ......... by induction hypothesis (1)
= 441m - (11^k * 7^2) + 1089m - (7^k * 11^2)
= 9{49m - (11^k * 7^2)/9 + 121 - (7^k * 11^2)/9}
which is divisible by 9



does that make sense?

Thanks

 

[Riviet]

= (9m - 11^k) * 7^2 + (9m - 7^k) * 11^2 ......... by induction hypothesis (1)
= 441m - (11^k * 7^2) + 1089m - (7^k * 11^2)
= 9{49m - (11^k * 7^2)/9 + 121 - (7^k * 11^2)/9}
which is divisible by 9

The problem with the last line is that we don't know if 11^k.49/9 or 7^k.121/9 are integers or not.
When using your assumption, you should only use a substitution once, ie in
7^k.7² + 11^k.11², pick one of the two terms that appear in your assumption (7^k or 11^k) rearrange the assumption to isolate that term you picked and substitute just that into the line. Let's say we pick 7^k and by rearranging the hypothesis we have:
7^k=9m-11^k
Substituting this:
7^k.7² + 11^k.11² = (9m-11^k).7² + 11^k.11²
=9.7².m - 49.11^k + 121.11^k
=9.7².m + 72.11^k
=9(49m + 8.11^k)
=9A, where A=49m + 8.11^k since m is a positive integer and k is a positive integer.
.'. 7^k.7² + 11^k.11² is divisible by 9.
.'. true for n=k+2.

 

[YBK]

The problem with the last line is that we don't know if 11^k.49/9 or 7^k.121/9 are integers or not.
When using your assumption, you should only use a substitution once, ie in
7^k.7² + 11^k.11², pick one of the two terms that appear in your assumption (7^k or 11^k) rearrange the assumption to isolate that term you picked and substitute just that into the line. Let's say we pick 7^k and by rearranging the hypothesis we have:
7^k=9m-11^k
Substituting this:
7^k.7² + 11^k.11² = (9m-11^k).7² + 11^k.11²
=9.7².m - 49.11^k + 121.11^k
=9.7².m + 72.11^k
=9(49m + 8.11^k)
=9A, where A is a positive integer since m is a positive integer and k is a positive integer.
.'.7^k.7² + 11^k.11² is divisible by 9.
.'. true for n=k+2.

ohh! I get it now.. thanks again mate!

 

[SeDaTeD]

Or without induction, by factorisation of the sum of 2 odd powers:
7^n + 11^n = (7 + 11)(7^(n-1) - 7^(n-2)*11 + 7^(n-3)*11^2 + ... - 7*11^(n-2) + 11^(n-1) )
= 18K, where K is that integer in the second bracket.

But knowing the exams, they'll insist you use induction for something that doesn't really need it.