Proof by Induction?

Day 1

100

The steps of proof by induction (steps 0-4).

What is 

0) Define the Proposition

1) Test n=1 (or whatever n starts at)

2) Induction Hypothesis (assume proposition is true)

3) Test n=k+1

4) Conclusion

200

Prove that 1+3+5+7+...=n^2 for all n≥1.

0) Let p(n) be the proposition that 1+3+5+7+...=n^2 for all n≥1

1) Basis Step n=1. (1^2)=1.

2) Assume that p(n) is true for n=k.

1+3+5+7+...=k^2

3) n=k+1. Goal: (k+1)^2

LHS: 1+3+5+7...+(2k-1)+(2(k+1)-1)

RHS: (k^2)+2k+1=(k+1)^2

4) Since p(1) is true, and if p(k) is true, p(k+1) is true, then p(n) is true for all n≥1. aka SPITA(PIT^3)FAN

Day 2

100

Define Divisibility

What is something that goes equally into another without a remainded

200

Prove by induction that (11^n) − 6 is divisible by 5 for all n≥1.

0) Let p(n) be the proposition that (11^n) − 6 is divisible by 5 for all n≥1.

1) Basis Step n=1

(11^1)-6=5, 11-6=5, 5=5

2) Assume p(n) is true for n=k

(11^k)-6=5m, where m is an integer

3) n=k+1

(11^(k+1))-6=11(11^K)-6

*11^k=5m+6*

11(5m+6)-6

55m+66-6=55m+60=5(11m+12), where 11m+12 is an integer.

4) SPITA(PIT^3) FAN

Day 3

100

Define Matrix

What is an array with rows and columns?

200

Let A = [1 0]

           [7 1]

Prove that A^n= [1 0]

                        [7n 1]

See paper for details

Day 4

100

Define Conjecture

a conclusion based upon incomplete information.

200

Find a formula for 7, 11, 15, 19... and prove.

4 is being added to each term, so slope is 4. You can then solve for b (mx+b).

7=4(1)+b, b=3

f(n)=4n+3

0) Let p(n) be the proposition that f(n)=4n+3 for 7, 11, 15, 19 for n≥1.

1) Basis step n=1. 

7=4(1)+3

7=7

2) Assume that p(n) is true for n=k

f(k)=4k+3

3) n=k+1. Goal: 4(k+1)+3

f(k+1)=4k+3+5

= 4(k+1)+3

4) SPITA(PIT^3)FAN

Bonus

500

Inductive Reasoning is typically used in this subject.

What is science