Question

How the heck do I do this induction proof?

Answer 1

should I prove n=0 as the base case?

Answer 2

\[\mathbb{Z}^+ \] are the integers starting with 1. So you need to use n=1 as your base case. Another reason why you should use n=1 as your base case is because the summation starts from i=1

Answer 3

@surjithayer

Answer 4

correct you should start for i=1

Answer 5

then assume for i=k
then prove for i=k+1

Answer 6

so for the base case 1 <= 1, therefore it holds?

Answer 7

k has to be a positive integer?

Answer 8

@Bobo-i-bo Do you know how i'm supposed to write out the inductive step?

Answer 9

So what is the hypothesis? Do you understand what i mean by my question?

Answer 10

your question?

Answer 11

for the hypothesis we assume i=k

Answer 12

and say that it should be equal to i=k+1 for the equation, but how do we plug in the k for the summation part?

Answer 13

Okay. So the hypothesis/assumption is that when i is equal to some number k, then
\[sum_{i=1}^{k}\frac{1}{i^2} \le 2-\frac{1}{k}\]
So we have to try and prove that if that is true for when i equal to that number k, then when i=k+1, the formula also holds, ie. that
\[sum_{i=1}^{k}\frac{1}{i^2} ]le 2-\frac{1}{k}\]

Answer 14

does that make sense?

Answer 15

umm not really

Answer 16

the second part, is confusing

Answer 17

sorry the latex didn't come out right, they were meant to say this:
\[\sum_{i=1}^{k}\frac{1}{i^2} \le 2-\frac{1}{k}\]
and
\[\sum_{i=1}^{k+1}\frac{1}{i^2} \le 2-\frac{1}{k+1}\]

Answer 18

Is that better? :P

Answer 19

Oh, yeah that makes more sense

Answer 20

The induction step is the idea that we do 2 things

1) Make an assumption that the formula holds true for any general case. We call this case k since we don't want to say something like "case 3". So in this part, we're assuming the formula holds true when n = k

2) after the step done above, we need to prove that the formula holds true when n = k+1. If we can show this, then it effectively shows that for any value of n, the next value of n works too. Imagine a row of dominoes. One knocks down the other one at a time. This is what the inductive step is in a sense

Answer 21

So we have the assumption, just need to prove that the formula holds now?

Answer 22

yes and you'll use the assumption to help prove the n=k+1 case

Answer 23

hint:

\[\Large \sum_{i = 1}^{k+1}\left[\frac{1}{i^2}\right]=\sum_{i = 1}^{k}\left[\frac{1}{i^2}\right]+\frac{1}{(k+1)^2}\]

Answer 24

So is that just algebra?

Answer 25

yes more or less

Answer 26

Also, this fact may help

If `a < b` then `b = a+m` where m is some real number such that `m > 0`

Answer 27

umm okay

Answer 28

I don't understand your first hint however

Answer 29

I broke up the summation pulling out the expression \[\Large \sum_{i = 1}^{k}\left[\frac{1}{i^2}\right]\]

Answer 30

this is to be able to use the assumption (the n=k case)

Answer 31

and the second part is the assumption?

Answer 32

the 1/(k+1)^2 part?

Answer 33

yup

Answer 34

no, the assumption sums from `i = 1` to `i = k` (since we stop when n = k)

Answer 35

the extra `1/(k+1)^2` added on is the n = k+1 case that we need to prove

Answer 36

oh alright

Answer 37

so now we have to prove both sides are equal?

Answer 38

let's start with the assumption (n = k case)

if we say

\[\Large \sum_{i = 1}^{k}\left[\frac{1}{i^2}\right] \le 2 - \frac{1}{k}\]

then that is the same as saying

\[\Large \sum_{i = 1}^{k}\left[\frac{1}{i^2}\right]+m = 2 - \frac{1}{k}\]

where m is some positive real number

Agreed? or no?

Answer 39

yes

Answer 40

because of this: iIf a < b then b = a+m where m is some real number such that m > 0

Answer 41

ok let's isolate the summation by subtracting m from both sides

\[\Large \sum_{i = 1}^{k}\left[\frac{1}{i^2}\right]+m = 2 - \frac{1}{k}\]

\[\Large \sum_{i = 1}^{k}\left[\frac{1}{i^2}\right] = 2 - \frac{1}{k}-m\]

Answer 42

This will be used later on. Let's now focus on the n=k+1 case

We need to prove the following

\[\Large \sum_{i = 1}^{k+1}\left[\frac{1}{i^2}\right] \le 2 - \frac{1}{k+1}\]

and we'll use the assumption to do this

Answer 43

with me so far?

Answer 44

yup

Answer 45

ok let's break up the summation on the left side

\[\Large \sum_{i = 1}^{k+1}\left[\frac{1}{i^2}\right] \le 2 - \frac{1}{k+1}\]

\[\Large \sum_{i = 1}^{k}\left[\frac{1}{i^2}\right]+\frac{1}{(k+1)^2} \le 2 - \frac{1}{k+1}\]

and we'll make a subsitution using the previous summation we solved for

\[\Large \sum_{i = 1}^{k}\left[\frac{1}{i^2}\right]+\frac{1}{(k+1)^2} \le 2 - \frac{1}{k+1}\]

\[\Large {\color{red}{\sum_{i = 1}^{k}\left[\frac{1}{i^2}\right]}}+\frac{1}{(k+1)^2} \le 2 - \frac{1}{k+1}\]

\[\Large {\color{red}{2 - \frac{1}{k}-m}}+\frac{1}{(k+1)^2} \le 2 - \frac{1}{k+1}\]

Answer 46

Sorry 1/(k+1)^2 added to the summation to break it up is because we're doing the k+1 case right?

Answer 47

correct

Answer 48

okay so what we have now has to somehow prove to be equal?

Answer 49

I'm thinking of how to do the next step. One moment

Answer 50

well I guess we can subtract 2 from both sides

\[\Large {\color{black}{2 - \frac{1}{k}-m}}+\frac{1}{(k+1)^2} \le 2 - \frac{1}{k+1}\]

\[\Large {\color{black}{2 - \frac{1}{k}-m}}+\frac{1}{(k+1)^2}{\color{blue}{-2}} \le 2 - \frac{1}{k+1}{\color{blue}{-2}}\]

\[\Large {\color{black}{- \frac{1}{k}-m}}+\frac{1}{(k+1)^2} \le - \frac{1}{k+1}\]

Answer 51

Then we can multiply both sides by -1. So to make the right side positive

\[\Large {\color{black}{- \frac{1}{k}-m}}+\frac{1}{(k+1)^2} \le - \frac{1}{k+1}\]

\[\Large -1*\left({\color{black}{- \frac{1}{k}-m}}+\frac{1}{(k+1)^2}\right) \le -1*\left(- \frac{1}{k+1}\right)\]

\[\Large \frac{1}{k}+m-\frac{1}{(k+1)^2} \ge \frac{1}{k+1}\]


side note: the inequality sign flips

Answer 52

oh okay

Answer 53

Notice how 1/k gets smaller as k gets larger (1/2 ---> 1/3 ---> 1/4 etc)

The general rule is this

1/k > 1/(k+1)

for any positive number k

Since `1/k > 1/(k+1)` we can say `1/k = 1/(k+1)+p` where p is some positive real number

Answer 54

so let's do that substitution and simplify a bit

\[\Large \frac{1}{k}+m-\frac{1}{(k+1)^2} \ge \frac{1}{k+1}\]

\[\Large {\color{red}{\frac{1}{k}}}+m-\frac{1}{(k+1)^2} \ge \frac{1}{k+1}\]

\[\Large {\color{red}{\frac{1}{k+1}+p}}+m-\frac{1}{(k+1)^2} \ge \frac{1}{k+1}\]

\[\Large \frac{1}{k+1}+p+m-\frac{1}{(k+1)^2} \ge \frac{1}{k+1}\]

\[\Large p+m-\frac{1}{(k+1)^2} \ge 0\]

Answer 55

sp p and m are both reals > 0?

Answer 56

hmm still thinking on how to wrap it all up though

Answer 57

yes

m > 0
p > 0

Answer 58

So do you need both?

Answer 59

I guess you could say q = p+m

then replace `p+m` with `q`

that would mean q > 0

Answer 60

a lot of variables being thrown in

Answer 61

let me see if there's another way to do this without adding in those extra variables

Answer 62

alrighty

Answer 63

ok do you agree that

\[\Large \sum_{i = 1}^{k}\left[\frac{1}{i^2}\right] = \frac{1}{1^2}+\frac{1}{2^2}+\ldots+\frac{1}{k^2}\]

Answer 64

How come?

Answer 65

the summation is shorthand for saying "sum these terms up"

so instead of saying `1+2+3+4+5+6+7+8` we can say \[\Large \sum_{i=1}^{8}i\]

Answer 66

Oh okay I get it

Answer 67

so saying

\[\Large \sum_{i = 1}^{k}\left[\frac{1}{i^2}\right] \le 2 - \frac{1}{k}\]

is the same as saying

\[\Large \frac{1}{1^2}+\frac{1}{2^2}+\ldots+\frac{1}{k^2} \le 2 - \frac{1}{k}\]

Answer 68

agreed? or no?

Answer 69

yes

Answer 70

but how does that help?

Answer 71

Sorry one second, it's taking a bit longer for me to format it

Answer 72

ok so I messed up and it's taking way to long to write out, esp with LaTex. I found this video here and it pretty much goes through it step by step.

So to avoid re-inventing the wheel, so to speak, it's probably better to watch it and follow that method

https://www.youtube.com/watch?v=S2tkLx019QI

Answer 73

Okay i'll check it out :)

Answer 74

the inductive step starts at about 1:57 roughly, so you can skip to that part (since we already have the base case nailed down)

Answer 75

If you follow from my previous comment, then we must prove that it works for i=k+1 from the assumption that i=k. Now let us just consider:
\[\sum_{i=1}^{k+1}\frac{ 1 }{ i^2 }\]

Answer 76

By defintion of the summation thing:
\[\sum_{i=1}^{k+1}\frac{ 1 }{ i^2 }=\frac{ 1 }{ 1^2 }+\frac{ 1 }{ 2^2 }+...+\frac{ 1 }{ k^2 }+\frac{ 1 }{ (k+1)^2 }=\sum_{i=1}^{k}\frac{ 1 }{ i^2 }+\frac{ 1 }{ (k+1)^2 }\]

Answer 77

Following me? Do you understand what we're trying to do currently? Can you see what to do next?

Answer 78

well we have to do the proof now

Answer 79

We are trying to prove that
\[\sum_{i=1}^{k+1} \leq 2-\frac{ 1 }{ k+1 }\]
But we are given that
\[\sum_{i=1}^{k}\frac{ 1 }{ i^2 } \leq 2-\frac{ 1 }{ k }\]
and i have given you the thing above. Does that help? :)

Answer 80

oops first inequality should be
\[\sum_{i=1}^{k+1}\frac{ 1 }{ i^2 } \leq 2-\frac{ 1 }{ k+1 }\]

Answer 81

okay

Answer 82

sorry kinda lost on what to do next

Answer 83

That's okay ^_^ Do you understand the concept of principle of induction?

Answer 84

Umm yeah i'm pretty sure i get it, i'm just thinking that the right side of the inequality should be that same as \[2-\frac{ 1 }{ k }+ \frac{ 1 }{ (k+1)^2}\]

Answer 85

because of the definition of summation thingy

Answer 86

Yup :D

Answer 87

give me a sec

Answer 88

but we want to have it look like \[2 - \frac{ 1 }{ k+1 }\] on the right side

Answer 89

oh okay sure

Answer 90

yup!

Answer 91

Sooo, wouldnt it be nice that perhaps
\[2 - \frac{ 1 }{ k } +\frac{ 1 }{ (k+1)^2 } \leq 2 - \frac{ 1 }{ k+1 }\] when \[k \geq 1\] Why not try and see if it's true/see if you can prove it. ;) ;)

Answer 92

Okie ill try, we just have to try simplifying the left side of the inequality right??

Answer 93

Hmm, you need to try and simplify the whole inequality to a point where you can infer for what values of k, the inequality holds

Answer 94

Umm okay, so how should I start?

Answer 95

Okay to start you off, you can minus 2 from both sides, then you can multiply both sides of the inequality by minus 1 (and remember to switch the sign of the inequality)

Answer 96

so we get this? \[\frac{1}{k}+m-\frac{1}{(k+1)^2} \ge \frac{1}{k+1} \]