Proof by mathematical Induction: Divisibility

In summary, Benny's solution is to use c to solve for k+1, which is 63(2^{6k}+3^{2k-2})-?=63(5A)-?=5B.
  • #1
DeathKnight
73
0
The question is: Prove by mathematical Induction that
[tex] f(n) \equiv 2^{6n}+3^{2n-2} [/tex] is divisible by 5. This is what I did:
Suppose that the given statement is true for [tex]n=k[/tex]
Since the[tex] f(k)[/tex] is divisible by 5,
[tex]f(k)=5A[/tex] (where A are is a constant.)
Also, from the given statement:
[tex] f(k)=2^{6k}+3^{2k-2} [/tex]
To prove that the given statement is also true for n=k+1:
[tex] f(k+1)-f(k) [/tex]
[tex]=2^{6k+6}+3^{2k} - (2^{6k}+3^{2k-2})[/tex]
[tex]=2^{6k}(63)+3^{2k-2}(8)[/tex]
After this I'm stuck! I know that I have to write it in the form of [tex]5B[/tex](where B is a constant) but I cant. This is because if I do take 5 common I get fractions in the above expression.
Thanks in advance for any help.
 
Last edited:
Physics news on Phys.org
  • #2
You should really start with a specific case. The statement is true for n = 1 since 2^6 + 3^0 = 65 is divisible by 5.
I find that the easiest approach for this problems is to start with the "n+1" expression where you replace n by n+1 and manipulate the expression to get it into the appropriate form.
[tex]
f\left( {n + 1} \right) = 2^{6n + 6} + 3^{2n}
[/tex]

We want something with 2^6n or 3^(2n-2). The former is clearly the easier of the two to incorporate into the above expression so try to get that in there first.
[tex]
= 2^6 \left( {2^{6n} } \right) + 3^{2n}
[/tex]

But you don't just want 2^6n in there somewhere do you? You'd much prefer to have 2^6n + 3^(2n-6) in there as well. So just add a 3^(2n-6) in the parenthesis with the 2^6n. Of course now you'll need to substract the relevant expression to maintain equality. From there it's just algebra, as with many questions of this type.
 
Last edited:
  • #3
DeathKnight said:
The question is: Prove by mathematical Induction that
[tex] f(n) \equiv 2^{6n}+3^{2n-2} [/tex] is divisible by 5. This is what I did:
Suppose that the given statement is true for [tex]n=k[/tex]
Since the[tex] f(k)[/tex] is divisible by 5,
[tex]f(k)=5A[/tex] (where A are is a constant.)
Also, from the given statement:
[tex] f(k)=2^{6k}+3^{2k-2} [/tex]
To prove that the given statement is also true for n=k+1:
[tex] f(k+1)-f(k) [/tex]
[tex]=2^{6k+6}+3^{2k} - (2^{6k}+3^{2k-2})[/tex]
[tex]=2^{6k}(63)+3^{2k-2}(8)[/tex]
After this I'm stuck! I know that I have to write it in the form of [tex]5B[/tex](where B is a constant).
You are almost there!
Benny is suggesting to use a very powerful solving technique: compare where you are to what result you need to get, and think of what would be nice to have as a stepping stone to close a gap.
Benny's solution mght be a little shorter, but since you've already come close to solution, let's continue.
Borrowing Benny's expression, you'd much prefer to see
[tex]2^{6k}+3^{2k-2}[/tex] in your
[tex]2^{6k}(63)+3^{2k-2}(8)[/tex].
Maybe, [tex]c(2^{6k}+3^{2k-2})[/tex], where c is a constant?
Say, [tex]c=63[/tex] (why?).
[tex]63(2^{6k}+3^{2k-2})=2^{6k}(63)+3^{2k-2}(63)[/tex].
It's not your [tex]2^{6k}(63)+3^{2k-2}(8)[/tex] yet, but you can make some adjustments.
[tex]f(k+1)-f(k)=63(2^{6k}+3^{2k-2})-?=63(5A)-?=5B[/tex]

Now, I am not sure why you started with
[tex] f(k+1)-f(k) [/tex].
You could:
[tex] f(k+1)=2^{6k+6}+3^{2k}=2^{6k}(64)+3^{2k-2}(9)= 64(2^{6k}+3^{2k-2}) - ? = 64(5A) - ? = 5B[/tex]
 
Last edited:
  • #4
Good day sir's , ireally want to understand the mathematical induction in your site.I really need your help to accomplish my course for four years.I hope my request won't be denied.Thank you very much
 

1. How does mathematical induction work?

Mathematical induction is a method of mathematical proof used to prove statements about a set of numbers, such as integers. It involves proving that a statement is true for a specific number, typically the first number in the set, and then showing that if the statement is true for one number, it is also true for the next number in the set. This process is repeated until it can be shown that the statement is true for all numbers in the set.

2. What is the principle of mathematical induction?

The principle of mathematical induction states that if a statement is true for the first number in a set and if the statement is true for the next number in the set whenever it is true for the previous number, then the statement is true for all numbers in the set. In other words, if the statement follows a pattern, it will be true for all numbers in that pattern.

3. How is mathematical induction used to prove divisibility?

To prove divisibility using mathematical induction, we first prove that the statement is true for the first number in the set, typically 1. Then, we assume that the statement is true for some arbitrary number, n, and use this assumption to prove that the statement is also true for the next number, n+1. This shows that if the statement is true for n, it is also true for n+1. By the principle of mathematical induction, this proves that the statement is true for all numbers in the set, and therefore the statement is true for all numbers in that set.

4. Can mathematical induction be used to prove all statements about divisibility?

No, mathematical induction can only be used to prove statements that follow a specific pattern or are true for all numbers in a set. It cannot be used to prove statements that do not follow a pattern or are only true for certain numbers in a set.

5. What are some common mistakes when using mathematical induction to prove divisibility?

One common mistake is incorrectly assuming that the statement is true for the first number in the set without actually proving it. Another mistake is assuming that the statement is true for n+1 without first showing that it is true for n. It is also important to make sure that the statement being proved is actually true for all numbers in the set, and not just a few specific numbers.

Similar threads

  • Precalculus Mathematics Homework Help
Replies
1
Views
728
Replies
13
Views
1K
  • Precalculus Mathematics Homework Help
Replies
6
Views
1K
  • Precalculus Mathematics Homework Help
Replies
17
Views
2K
Replies
5
Views
2K
  • Linear and Abstract Algebra
Replies
2
Views
881
  • Calculus and Beyond Homework Help
Replies
8
Views
927
  • Precalculus Mathematics Homework Help
Replies
12
Views
1K
  • Precalculus Mathematics Homework Help
Replies
6
Views
1K
  • Precalculus Mathematics Homework Help
Replies
15
Views
1K
Back
Top