Precal Question

[Slaughter]

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.

[Yoni]

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...

[Slaughter]

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.

[MyndFyre]

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.   

[Yoni]

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.

[Slaughter]

Ok, thanks Yoni.

Q.E.D. = ? Maybe it's something simple, but it's meaning escapes me.

[Yoni]

Quod Erat Demonstrandum.

From Latin: That which was to be proven.

http://mathworld.wolfram.com/QED.html

[Ender]

Interesting. I have a question about inductive reasoning...

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.

[Yoni]

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.