Eh, problem on my homework, causing a bit of confusion.
Use mathematical induction to prove the given proerty for all positive integers n.
A factor of (2^2n-1 + 3^2n-1) is 5.
I've got this far: (2^2k-1+3^2k-1) ?= 5*m
I'm not really sure where to go from here based on knowledge of other mathematical induction proofs.
Induction is:
Given a proposition P(n) (a proposition P that talks about an integer n), proving by induction that the proposition is TRUE for all positive integers is:
1) Proving that P(1) is true, that is, the proposition is true for n = 1.
2) Showing that P(k) => P(k + 1) for every positive integer k. That is:
2.a) Assume P(k) is true, that is, the proposition is true for n = k for some positive integer k.
2.b) Based on the assumption "2.a", prove that P(k+1) is true, that is, the proposition is true for n = k + 1.
Looks like you haven't really started. Try again...
Well, I skipped a couple of steps actually typing in here... I'm on the 3rd step, letting n = k+1, but I'm not sure how to set it up to actually prove the two equations are equal - from here I believe it's just algebraic, but I'm not exactly sure... Anyway:
let n=1
5 = 5
let n=k, assume true
(2^2k-1+3^2k-1)=5*n for some integer n.
let n = k+1
2^2k+1 + 4^2+1 ?= 5*M
From here, I'm not really sure where to go...let me know if I botched anything up with the above steps.
Edit: I see I had botched typing in the first post - I typed 2^2k-1 instead of 2k+1 for both.
This is precalculus? I don't think I would have gotten into stuff like this until linear algebra in college, had I stuck with engineering.
Either that, or I just don't remember it. :o
Proposition:
For every positive integer n, [2^(2n - 1) + 3^(2n - 1)] / 5 = some integer.
1) Proof for n = 1:
[2^(2*1 - 1) + 3^(2*1 - 1)] / 5 = (2^1 + 3^1) / 5 = 5/5 = 1 = some integer.
2.a) Assumption for n = k:
We assume that it is true that [2^(2k - 1) + 3^(2k - 1)] / 5 = some integer.
2.b) Proof for n = k + 1:
[2^(2k + 1) + 3^(2k + 1)] / 5 = [4 * 2^(2k - 1) + 9 * 3^(2k - 1)] / 5 =
= [4 * 2^(2k - 1) + 4 * 3^(2k - 1)] / 5 + [5 * 3^(2k - 1)] / 5 =
= 4 * [2^(2k - 1) + 3^(2k - 1)] / 5 + 3^(2k - 1) =
= 4 * (some integer, by the assumption in 2.a) + 3^(2k - 1) =
= integer * integer + integer = integer.
Q.E.D.
Ok, thanks Yoni.
Q.E.D. = ? Maybe it's something simple, but it's meaning escapes me.
Quod Erat Demonstrandum.
From Latin: That which was to be proven.
http://mathworld.wolfram.com/QED.html
Interesting. I have a question about inductive reasoning...
Quote from: Yoni on April 11, 2005, 03:18 PM
Induction is:
Given a proposition P(n) (a proposition P that talks about an integer n), proving by induction that the proposition is TRUE for all positive integers is:
1) Proving that P(1) is true, that is, the proposition is true for n = 1.
2) Showing that P(k) => P(k + 1) for every positive integer k. That is:
2.a) Assume P(k) is true, that is, the proposition is true for n = k for some positive integer k.
2.b) Based on the assumption "2.a", prove that P(k+1) is true, that is, the proposition is true for n = k + 1.
Is the first step necessary, or is it just a quick way of saving yourself work if the claim is false? My reasoning concludes that it's not. First you make the assumption that this holds true for any positive integer k (the set of values you are testing). If P(k) is true, then so would P(k+1), and since k+1 can represent any positive integer, this in effect means that P(k) is true, where n is any positive integer. I know the rule: if a then b then not necessarily if b then a but in this case this reasoning holds true since the only way that P(k+1) is true is that P(k) is also.
Quote from: Ender on November 11, 2005, 09:42 PM
Is the first step necessary, or is it just a quick way of saving yourself work if the claim is false?
Hmm, let's leave it out and try a nice proof.
The integer sequence A(n) satisfies: A(n+1) = A(n) + 2.
Prove by induction: All the integers in the sequence are even.1. Assume A(k) is even for some k. Then A(k+1) = A(k) + 2. Since A(k) is even and 2 is even, then so is A(k)+2, i.e. A(k+1) is even. Therefore by induction, A(n) is even for all n. Q.E.D.
Prove by induction: All the integers in the sequence are odd.1. Assume A(k) is odd for some k. Then A(k+1) = A(k) + 2. Since A(k) is odd and 2 is even, then A(k)+2 is odd as well, i.e. A(k+1) is odd. Therefore by induction, A(n) is odd for all n. Q.E.D.