Question

how is principle of mathematical induction actually a prove?
lets say we have
summation of something = a conjecture
what are we actually proving?
i dont really see it..

Answer 1

Good question. Mathematical induction proves the conjecture by first showing it is true for one case, then showing that for any case, the truth of that case implies the truth of the next case.

Answer 2

ok but there are is a right hand side equals to a left hand side..
how is it actually proving? proving what is true? the left or the right?

Answer 3

The example you gave:

summation of something = a conjecture

Is not a proof by induction.

Answer 4

yes ok..

Answer 5

It's just a conjecture that you might be able to prove using induction.

Answer 6

but why does a conjecture have two sides

Answer 7

what is the summation there for?

Answer 8

Because you (in this case) are trying to PROVE that the sum of some sequence equals something

Answer 9

So the equal sign is there because that's what you're assuming is true.

Answer 10

It could be a less than, or greater than sign.

Answer 11

it could be all sorts of things.

Answer 12

so we're trying to prove that the statement itself is true?

Answer 13

Just depends on what we want to show.

Answer 14

Yes

Answer 15

how did that statement even come about?

Answer 16

Induction is perfectly reasonable.

If \(P(1)\) and \(P(n) \implies P(n+1)\)
Then for any \(k\) we can get from \(P(1)\) to \(P(k)\)

Suppose we want to show something is true for some \(k\).
Since \(P(1)\) and \(P(n) \implies P(n+1)\) then
\[P(1) \implies P(2)\]\[P(2)\implies P(3)\]...
\[P(n -1)\implies P(n)\]

Answer 17

A lot of times, it starts off with a guess. We might notice something that seems reasonable. We can make a guess, then prove that it's true with induction.

Answer 18

ok.. i appreciate your answer but i dont seem to get it in symbol terms seems to confuse me

Answer 19

P is any proposition you want to show holds for all natural numbers.

Answer 20

whats propostion

Answer 21

Something that might be true.

Answer 22

It is a logical/mathematical statement.

Answer 23

ok......
i have this question can you go through with me the steps to prove?

Answer 24

We can certainly try.

Answer 25

it's summation from r=1 to n r^2= 106n(n+1)(2n+1)

Answer 26

Sorry correction to the last line of my previous post. Should be: \[P(k-1) \implies P(k)\]

Answer 27

i mean 1/6

Answer 28

it's summation from r=1 to n r^2= 1/6n(n+1)(2n+1)

Answer 29

so what are we showing that is true? the summation part?

Answer 30

\[\sum_{r=1}^n r^2 = \frac{n(n+1)(2n+1)}{6}\]

Answer 31

This?

Answer 32

yes!

Answer 33

Ok, so you want to prove it?

Answer 34

yes! how do i start?

Answer 35

Start by showing the base case is true.

Answer 36

Show its true for n=1

Answer 37

\[\sum_{i=1}^{1}r^2=1^2=1=\frac{1(2)(3)}{6}=\frac{1(1+1)(2(1)+1)}{6}\]

Answer 38

what is a base case

Answer 39

The base case is 1

Answer 40

You start by showing it's true for some initial n. In this case 1 works fine.

Answer 41

now assume it is true for some k integer

Answer 42

to which side the left or the right

Answer 43

both

Answer 44

Show that if it is true for n, it is true for n+1.

Answer 45

can i just listen to one person talk?

Answer 46

Certainly.. Do you have a preference?

Answer 47

i'd prefer polpak hahah

Answer 48

='(

Answer 49

sorry to the rest

Answer 50

bah. Just cause I'm in green ;p

Answer 51

Not fair

Answer 52

no.. u started with the equation!

Answer 53

lets continue and not waste time!

Answer 54

It's just sad cause this is one of the more fun problems we get, so the good tutors are champing at the bit ;)

Answer 55

WAIT CAN I ASK AGAIN WHAT ARE WE PROVING?

Answer 56

haha..

Answer 57

We are trying to prove this:
\[\sum_{r=1}^n r^2 = \frac{n(n+1)(2n+1)}{6}\]

Answer 58

which means we want to prove the right equals to left?

Answer 59

And for completeness (and simplicity later) I'll modify it slightly:

\[p(n) :\sum_{r=1}^n r^2 = \frac{n(n+1)(2n+1)}{6}\]

Answer 60

Yes exactly. We need to prove that the left equals the right, for any n you want to choose.

Answer 61

ok! so we start by n=1?

Answer 62

yes, we have to start with a base case

Answer 63

base case=smallest integer?

Answer 64

So plug 1 into the left side, and into the right side and see that they're equal.

Answer 65

smallest natural number.

Answer 66

yes they are equal but you cant assume that since they are true for both sides you cant conclude that pattern is true you have to continue proving by plucking more numbers?

Answer 67

You can't keep plucking numbers. There might be one that it's not true that you don't pick.

Answer 68

so instead we use k?

Answer 69

Instead you have to show that it being true for k means it MUST be true for k+1 and then you have it being true for all numbers.

Answer 70

so k is any number??

Answer 71

why not k-1 why k+1

Answer 72

Because the summation starts at 1 and goes t n, so n has to be bigger than (or equal to) 1 to make sense. So we need to prove for 1 and go up.

Answer 73

if you wanted to subtract 1 you'd have to start at something big, but there's always a next bigger number to start at.

Answer 74

ok the next statement says assume Pk is true for some kweird sign Z plus

Answer 75

meaning?

Answer 76

hehe.. That wierd sign is \(\in\) and it means 'in'. the \(\mathbb{Z}^+\) means positive integers.

Answer 77

so! k is one of the positive integer?!

Answer 78

Yes, we want to show that p(k) is true for any k that is a positive integer.

Answer 79

ok! cool!

Answer 80

What is p(k)

Answer 81

uh huh!

Answer 82

so now instead of n we write all as k?!

Answer 83

yes.

Answer 84

we are assuming that that is true?

Answer 85

Actually if you want we can skip writing p(k). But we'll assume it is true.

Answer 86

ok! cool so next we got to prove the k+1 term??

Answer 87

my book says we have to write it..

Answer 88

ok fair enough.

Answer 89

lets prove the k+1 term now

Answer 90

Okey

Answer 91

summation of r=1 to (k+1)???

Answer 92

why the last term (k+1)

Answer 93

and why is it want to show

Answer 94

want to show that is it actually also equals to that??

Answer 95

Right. We can show that IF we assume it's true for p(k) then it must be true for p(k+1)

Answer 96

oh you assumed that Pk is true!

Answer 97

Now we are gonna make the assumption that it's true for p(k) which is the sum from 1 to k

Answer 98

why = 1+2+3+............