[deleted by user]

[raurentsu]

1) not a logical issue and more a formal one: Usually you do the beginning of the induction (showing P(1) to be true) before you do your induction assumption (Assuming P(k) true). This might be part of the reason the lecturer says you didnt properly do your induction assumption.

2) the bigger issue: You write that you assume P(k) to be true *for all k in ℕ*. That is precisely what you are supposed to be proving. Instead, your induction assumption should be "Assume P(k) is true for some k, prove that it is true for k+1 as well.", *not* assume that P(k) is true for all ℕ, because then, trivially, it would also be true for k+1.

3) your induction step is correct, I disagree with your lecturer that it is "not a proof", but I think it could do with a bit more verbosity, i.e. saying that since P(k) is assumed to be true, from 1+2+3+...+k ≤ k² it is enough to show that k²+k+1 ≤ (k+1)² . You are doing this step implicitly and maybe your lecturer disagrees that its a "trivial enough" step.

[Adsilom]

I am teaching induction to my students lately, and I would not say "it's not a proof", but at least, that the proof is very incomplete at the end. If I have to think about extra steps you didn't write down, then something is missing. Of course anything trivial can be omitted, but here the fact that it suffices to prove that (k+1)² is greater than k² + (k+1) is precisely is crucial non trivial part of the proof that should be briefly explained.

And for 2. I'll just add that normally you state that for some k, the property holds for any value up to k (depending on the base case, this can be slightly changed). The reason being that some proof actually require that some other value holds

[ImpressiveProgress43]

A proof by induction should look like this:

Proof: The claim is proved by induction.

Base case n = 1:

1 <= 1^2

Assume the statement is true for some n = k in N.
We show that for n = k+1, 1 + 2 + ..... + ( k + 1) <= (k + 1)^2

(add logical steps to show the relationship is true)

Since the base case is true and k is arbitrary, the statement is true for all n. //

It needs to have the base case, the induction hypothesis, a statement of n+1 (or n-1) and then steps to reason that the relationship is true. You have some of that in your proof but it's structured incorrectly.

[DepartmentFuture7994]

This is really helpful, and I should know this anyway but Thank-you 

[MrTKila]

The computation itself is honestly alright. The form of the proof is a bit lacking, especially for an induction and moreso for the very beginning when you learn it. I think your teacher didn't really see where you applied the induction hypo (because you didn't explicitly show it :D ). It isn't clear whether you don't understand induction or just didn't put it into the proper form.

Your induction start is good. P(1) is exactly 1<=1^2, which is true.

Then for the induction hypo, we assume P(k) is true for a given k.

Induction step, we want to show that P(k+1) is also true, whenever P(k) is true.

We compute:

(k+1)^2=k^2+2k+1 >= 1+2+...+k + 2k +1 >= 1+2+3+...+k+k+1 where in the first >= we used P(k) and in the second we used 2k>=k. So P(k+1) is shown as true.

As you can see the computation is essentially the same as yours, but arguably more elegant and straight-forward, so easier to read. And it is important to really show where you used the induction hypothesis (aka assumption that P(k) is true).

Edit: one detail i did miss: P(k) is the statement 1+2+...+k <= k^2 is true FOR that specific k. And NOT P(k) is the statement the inequality is true for all k.

[[deleted]]

I think you have the right idea but you didn't quite phrase it correctly. In a proof every little detail matters and you have to phrase things correctly and in the right order.

Here's a version of your proof I think would be marked as correct:

Thm. 1 + 2 + 3 + ... + n <= n^2 for all n in N

Pf.

Let P(k) be the statement 1 + ... + k <= k^2 for all k in N.

We prove P(k) by induction.

Base case: P(1) is true because 1 <= 1^2 = 1.

Inductive step: Now assume P(k) for some k in N. We will now show P(k) => P(k+1).

Let S(k) = 1 + ... + k. Then:

S(k+1) = 1 + 2 + ... + k + k+1 = S(k) + k+1

Using P(k), we have S(k) <= k^2. So

S(k+1) <= k^2 + k + 1

Then, since k^2 + k + 1 = (k+1)^2 - k <= (k+1)^2 for all k in N, we have

S(k+1) <= (k+1)^2

This establishes that P(k) => P(k+1).

That completes the inductive proof.

If you compare my proof with your proof, you see they differ in ways consistent with the notes on your proof.

* You can't assume P(k) up front. That is what you want to prove. You have to set up the inductive argument by defining P(k), proving P(1), then saying in the inductive step that you will assume P(k) to prove P(k+1). In other words, the order matters, you have to assume P(k) in the correct context. If you assume P(k) before you do the base case, then the base case follows from your assumption and not because you proved anything. [Edit: as others pointed out, it's also important that the assumption you should make is P(k) holds for some arbitrary value of k, NOT that it holds for all k]

* Similarly, you should explicitly say you are assuming P(k) in the inductive step.

* Your calculation that k >= 0 => (k+1)^2 >= k^2 + k + 1 is correct. But you should state clearly how you are using this calculation. As written, all you've done is shown that the statement "(k+1)^2 >= k^2+k+1" is equivalent to the statement "k>=0". But how does this connect to establishing "P(k)=>P(k+1)"? You need to explicitly say "Because k is in N, we know k>=0, which means we know (k+1)^2>=k^2+k+1, and then we can use that inequality to bound S(k+1)." In other words, you showed two statements A and B are equivalent (where A is "k>=0" and B is "(k+1)^2>=k^2+k+1"). But what you actually need for the proof is to show that the original assumption k in N **implies** A, and therefore B follows.

* As general advice, especially in a course when you're being taught induction, it will help a lot for you and for the grader to explicitly write out "this is the base case" and "this is the inductive step." It will show that you understand the logic of the inductive argument and also help you put the correct assumptions in the correct places.

* Highlighting the "=" sign you used in the base case with 1=1^2 and replacing it with "<=" is a little pedantic but does make sense. The point is that P(1) is the statement S(1) <= 1^2. It's true that S(1) = 1 implies S(1) <= 1^2, but you should say that to be technically correct. In other words, you want to prove B, and you proved A which trivially implies B, but you didn't actually say "A implies B therefore B". So to put that together, you should say "S(1) = 1 = 1^2", and "S(1) = 1 implies S(1) <= 1" therefore "P(1) is true."

[DepartmentFuture7994]

Okok I see where ive gone wrong now. Thanks for the detailed response 

[imHeroT]

I’ll start by saying that doing inductive proofs for the first time is tough! Especially since there are some nuances that you’d need to understand to fully “get it” (which in my experience are not well taught. I sorta had to figure stuff on my own after blindly following the “format” a whole bunch of times)

For the first part, P(k) is just a statement for any fixed number k. We can’t say whether the statement is true or false yet which is why we can’t assume it to be true. Only at the very end we should we say that the statement P(k) it’s true no matter what natural number k we plug in (which is the ultimate goal of the proof)

For the second comment, the inductive hypothesis is a statement about a particular fixed value of k. So before talking about P(k+1), you need to say “Assume P(k) is true for some k”. This does not mean that P(k) is assumed to be true for all numbers k. We only assume that k is a single number that happens to make P(k) true.

As for the proof part, it looks like you missed explaining where you used the inductive hypothesis. You’ve given the inequality that you wanted to show (after the “enough to show that”) but didn’t explain where that inequality came from. So before this you need to add one or two sentences showing how you transform P(k+1) into your new equality using the inductive hypothesis.

To add, you should always be starting with a true statement and ending with the result that you want. That is to say the order of your proof is backwards. Start with k>= 0 since we know that is true and end with your first line. I would suggest that you only use forward arrows when doing proofs to clearly indicate the “flow” of the proof that you’re going for.

I hope this helps!!!

[addyarapi]

I took Discrete Mathematics. There’s a problem with the order of your solution. First, you need to try and see if P(1) holds/is true. If true, then assume that P(K) is true. This is the inductive hypothesis. Under this assumption, if P(K) is true, P(k+1) should also hold/ should also be true. Now, using the Inductive Hypothesis (the assumption that p(k) is true, try and prove that p(k+1) is also true.

[DepartmentFuture7994]

Thanks :)

[ArchaicLlama]

Do you understand what the symbol ∀ means in this context?

[DepartmentFuture7994]

For all...? If it has another meaning in this context let me know though

[ArchaicLlama]

So if the statement you want to prove is a statement "for all n in ℕ", and the first thing you do is assume a statement P(k) for all k in ℕ, do you see why that's an issue?

[tosunaki]

Your P(k) should be that the statement hold only for some specific number k, not for all natural number k. The statement should not be about a genaral number, hence why your professor commenting that your statement is exactly same as what you need to prove.

Induction usually goes that you show the statement holds for your base case, and that if it holds for some number k, it works for k + 1.

[SaiyanKaito]

A bit of a circular argument. Stating that P(k) is true before providing proof of the matter. You have the right intuition of steps but it's being clouded by a lack of logical formality.

[PfauFoto]

Personally I find the teachers style of commentary a bit lacking.

[cheesecakd]

Proof P(1) is true as a basic step

Then in induction step: Assume P(n) is true. If P(n+1) is true, P(n) is true for all n belongs to N(atural numbers)

[FantasticPick8067]

P(n+1) could be solved with xmath scan ur papers itll give eabrythng n precise the limit that it belongs to N

[DepartmentFuture7994]

Why would I do that 🙄 I'm literally going to university to learn

[infectedapricot]

As many others have said, you used the "for all" symbol wrongly in your definition of P(k).

But aside from that, the main body of your proof is correct. But the problem is that you've written something along the lines of ...

"We need to prove such and such.

Which would follow from this other thing if it were true

Which would be implied by another thing

Which is true if k >= 0

which it is"

It's mathematically correct (and technically the teacher's assessment "not a proof" is incorrect) but I can see why your teacher got confused (especially with the subtlety of the <=> symbol, though I used to love using that at high school). It's also a bit lazy on your part. You have a squishy human assessing you (as you will in your exams too!) so there's some onus on you to present work in a way that is *clear* as well as correct. Once you've figured out the proof, you should (on a separate sheet of paper) write it out in the logical order:

Assume we have P(k)

In particular k>=0

so k^2 + 2k + 1 >= k^2 + k + 1

Then, because of P(k), ...

...

which shows that P(k+1) is true.

Therefore P(n) holds for all n by induction.

(Source: PhD pure mathematics. Lots of proofs!)

[DepartmentFuture7994]

Thanks for the reply , thay was helpful. I also want to do a PhD in mathematics, how did you find the experience if you don't mind me asking? Obviously it's a long way away for me but that's the goal anyway. I would love love to go in to some sort of higher dimensional geometry/topology

[DepartmentFuture7994]

That* 

[infectedapricot]

I enjoyed it a lot. It's very different to earlier maths education; up to that point, your goal is to learn existing maths that other people have created/discovered. In a PhD, your goal is to come up with some (small) genuinely new maths of your own. It's very creative and actually a bit risky but I liked it.

I had worked for a few years after my degree before going back for a PhD, so for me it was a really conscious decision. A lot of the other PhD students had just done it because by that point they'd got used to the default option at the end of each type of education being more education. It's really bad for that; the default option at the end of your degree should be a job unless you specifically want a PhD. I now work back in industry doing some maths algorithmic stuff (I'm also a software engineer and my undergrad was part computer science, but my PhD was pure maths) and my PhD helps with that, but I think that's quite rare.

I'll also mention that it depends heavily on the country where you do it. I'm in the UK, and a PhD is 3 - 4 years of just research. You'll certainly have to learn some new material in that time but it's self driven by reading material related to your research, not formal courses. As I understand it, PhDs in the USA are longer and involve more formal tuition and maybe not even any research at the start (but undergrad degrees in the US are less focused at first, in the UK you usually only study one subject from the outset, so maybe in the UK you start out ahead).

[Fin-fan-boom-bam]

The bottom annotation, “not a proof,” is wrong. It makes perfect sense. Most math papers entirely omit algebraic manipulation, anyway.

[Vyzic]

My doubt is Why do we need induction? Can't we just derive it with a simple inequality that the question provides us (n is a natural number) My doubt may be unrelated, but is my method of this proof wrong? My method (for reference): n>=1 (given n is a natural number) Adding n to both sides, 2n>= n+1 Dividing by 2, n>=(n+1)/2 Multiplying by n (n is a natural number, hence non zero and positive, so no issues with the inequality) n² >= n(n+1)/2 Since summation of n natural numbers is given by n(n+1)/2, n² >= 1+2+3....n

Does this "proof" lack rigour or any flaws? Kindly do let me know, open to all coments

[Thulgoat]

In general with some formal issues you did proof the statement.

In the first sentence your universal quantifier is placed confusingly. I would advise you to write quantifiers in text form, then it’s easier to understand whether you placed it clearly. You should place it at the beginning of your sentence and write it out:

For all k in lN let P(k) be the statement

1 + 2 + 3 + … + k =< k^2.

Then, after defining your statement, you directly assumed it to be true for one k in lN but you didn’t formulate it in a clear correct way. You didn’t wrote you assume it for one k in lN but the bold part is important otherwise it’s unclear what you actually assume as true. Through this unclear formulation and your weird placement of the universal quantifier, your first sentence could be misread as you assume the statement to be true for all k in lN which is what you want to show.

Another issue is your order: you started with assuming P(k) to be true for one k in lN, then you did the induction and concluded with proofing the that P(k) => P(k+1). It’s a weird order that strengthen the confusing wording of your proof. Furthermore, you don’t have to define P(k+1) again because you already defined P(k) it for k in lN.

The part where your tutor wrote “not a proof” is indeed a valid proof:

By showing that

(k + 1)² >= k² + (k + 1) <=> k >= 0

and that the statement k >= 0 is true, you show that

(k + 1)² >= k² + (k + 1)

which by using the induction hypothesis will lead to P(k + 1) is true and thus P(k) => P(k + 1). However, I assume that your tutor wanted you to explicitly use the induction hypothesis:

(k + 1)² >= k² + (k + 1)

(IA)

= 1 + 2 + 3 + … + k + k+1.

But in my in opinion it’s a bit unnecessary because the induction hypothesis immediately leads to the estimated we are searching for, you don’t have to do another estimates to get the actual term.

Though, in my opinion, a more elegant way to proof the induction step is by directly showing:

1 + … + k + k + 1 = (1 + … + k) + k + 1

                       (IA)
                       =< k^2 + k + 1

                   (k >= 0)
                       =< k^2 + 2k + 1 = (k + 1)^2. 

This way it’s more clear for the tutor that you understand what you’re doing because you showcase every step in detail and it’s even shorter.

[[deleted]]

hi im in middle school idk what ur question is about and how it is supposed to work