Problem

[mastaguybi]

Prove for any positive integer x, the value of the expression
3^(2x+2) - 8x -9 is divisible by 64 :ehh: :) :eek2:

[eranga262154]

First of all, welcome to the forum:) :)

Use mathematical induction method to solve this.

[eranga262154]

Step 1:

Check that x = 1, the requirement is satisfied.

f(x) = 3(2x + 2) - 8x - 9
f(1) = 3(2(1) + 2) - 8(1) - 9
f(1) = 64

So divisible by 64.

Step 2:

Assume that x = n, (n >= 1) satisfied the condition,

f(x) = 3(2x + 2) - 8x - 9
f(n) = 3(2n + 2) - 8n - 9 ------- (A)


Step 3:

Prove that x = (n + 1) satisfied the condition,

f(x) = 3(2x + 2) - 8x - 9
f(n + 1) = 3(2(n + 1) + 2) - 8(n + 1) - 9
f(n + 1) = 3((2n + 2) + 2) - 8(n + 1) - 9
f(n + 1) = 3(2n + 2)*32 - 8(n) -8 - 9
f(n + 1) = 9 * 3(2n + 2) - 8(n) -17 ------ (B)

(A) - (B),

f(n + 1) - f(n) = 8 * 3(2n + 2) - 8 ------ (B)

this should be the first term, right. So f(n + 1) - f(n) = 64.

For all the positive values satisfied the given condition.

[jemidiah]

eranga262154, I completely agree that this should be done with induction. However, I don't quite get your last step where you say that f(n+1) - f(n) = 64, mostly because f(3) - f(2) = 5824 (though 5824 is divisible by 64 if that's what you meant).

Lemme briefly explain induction first. A proof by induction is usually where you know your goal (in this case, you know that the given function is divisible by 64 for positive integer values of x) and you're just trying to prove it. To prove whatever your goal is, you first state that it is true in some "base case": here, you want to prove that f(1) is divisible by 64.

The final step in a proof by induction is stating that, if the goal is true in some case, it follows that the goal is true in the next case. Here, that means that, if f(n) is divisible by 64, then f(n+1) is certainly divisible by 64. Then, for any (positive integer) value of n you choose, you can get a long chain of implications so that the goal is definately true for that values of n.

For example, here, if you knew that f(1) was divisible by 64 and, if f(n) is divisible by 64 then f(n+1) is too, you know that f(4) is divisible by 64 since:
f(1) is divisible by 64 from the base case [which we brute forced]
f(2) is divisible by 64 since, if f(1) is divisible by 64, then f(1+1)=f(2) is divisible by 64 as well
f(3) is divisible by 64 since, if f(2) is divisible by 64, then f(2+1)=f(3) is divisible by 64 as well
f(4) is divisible by 64 since, if f(3) is divisible by 64, then f(3+1)=f(4) is divisible by 64 as well
...
f(n-1) is divisible by 64 since, if f(n-2) is divisible by 64, then f(n-2+1)=f(n-1) is divisible by 64 as well
f(n) is divisible by 64 since, if f(n-1) is divisible by 64, then f(n-1+1)=f(n) is divisible by 64 as well


Alrighty, here's the proof in this case:

Base Case:
f(1) = 3 ^ (2 * 1 + 2) - 8 * 1 - 9 = 3^(4) - 8 - 9 = 81 - 8 - 9 = 64, which is divisible by 64

Inductive Hypothesis / Recursive Step: (prove that, if f(n) is divisible by 64 [that is, f(n) = 64q(n) for some positive integer q(n)], then f(n+1) is divisible by 64 [that is, f(n+1) = 64p(n) for some positive integer p(n)]).

Assume f(n) is divisible by 64.
Then f(n) = 32n+2 - 8n - 9 = 64q(n)
Now f(n+1) = 32n+4 - 8n - 17 = 32 * 32n+2 - 8n - 17 = 9*(32n+2 - 8n - 9) + 72n - 8n + 81 - 17 = 9*f(n) + 64n + 64 = 64(9q(n)+n+1) = 64p(n) as desired. p(n) is clearly always an integer for integer values of n.


Since f(1) is divisible by 64, the proof is complete. Yay!

[eranga262154]

eranga262154, I completely agree that this should be done with induction. However, I don't quite get your last step where you say that f(n+1) - f(n) = 64, mostly because f(3) - f(2) = 5824 (though 5824 is divisible by 64 if that's what you meant).

Correct:thumb:

To use induction method we use different way. I shows that when x>1, we can prove two consecutive terms directed to the first term.