/sci/ - Science & Math » Thread #14244657

34KiB, 660x473, 1614188138041.png

View Same Google iqdb SauceNAO

Anonymous Sat 19 Feb 02:52:14 2022 No.14244657 View Reply Original Report

Quoted By: >>14244670 >>14244770 >>14244822 >>14245513 >>14245524 >>14245645 >>14245923 >>14245958 >>14246171 >>14247445 >>14247471 >>14247715

>Have something to prove
>Decide to use induction
>Assume that for an arbitrary number a proposition is correct
>Use the starting proposition to prove stuff
>Literally I assumed something is true to prove other stuff is true
>Thus conclude that this is true for every number greater than the starting one
why is this allowed?

It's like building a house on sand and expecting it to hold, it just makes no sense, there is no point in using it because you assume something is true and then extend it to everything..

Anonymous

Anonymous Sat 19 Feb 2022 02:58:27 No.14244670 Report

Quoted By: >>14244677 >>14247715

>>14244657
>Have something to prove
>Assume that for an arbitrary number a proposition is correct
>QED
based

Anonymous

Anonymous Sat 19 Feb 2022 03:01:13 No.14244677 Report

Quoted By: >>14247715

>>14244670
correct. There is literally nothing wrong with this. Keep coping OP

Anonymous

Anonymous Sat 19 Feb 2022 03:30:41 No.14244741 Report

Quoted By: >>14247715

The informal intuition behind induction on the naturals is that you could technically show that P(n) holds for an arbitrary n by finite applications of Modus Ponens. P(0) holds. But P(0) implies P(1), so P(1) holds by MP. But P(1) implies P(2), so P(2) holds by another application of MP.

A formal proof depends on what kind of system you're working in. In set theory for example the induction principle for the finite ordinals, which when equipped with successor mapping and empty set form a model of Peano arithmetic (second order even), follows directly from their construction as the least set containing the empty set and closed under the successor mapping ("the least inductive set").

Anonymous

Anonymous Sat 19 Feb 2022 03:47:02 No.14244770 Report

Quoted By:

>>14244657
Well you forgot the base case, usually n =1.
There's nothing wrong logically with considering the hypothetical case of $P_n$ being true and then use that to imply that $P_{n+1}$ . You still have to show that there IS a number were it is true, which is your base case.

Anonymous

Anonymous Sat 19 Feb 2022 04:15:35 No.14244822 Report

Quoted By:

>>14244657
You have to explicitly show it's true for the first case, then show the previous case being true implies the next case is true

Anonymous

Anonymous Sat 19 Feb 2022 04:44:03 No.14244872 Report

Quoted By:

>step 1: show that "case N true => case N+1 true"
>step 2: show that "case N" is indeed true
thats it. youve now shown it for all possible N. is it not really fucking obvious why this is allowed? I always thought the idea of mathematical induction was a super slick (and valid) logical trick, do you see it too?

Anonymous

View Same Google iqdb SauceNAO 1519051260290.jpg, 8KiB, 200x200

Anonymous Sat 19 Feb 2022 05:05:47 No.14244915 Report

Quoted By: >>14244920 >>14244971 >>14245522 >>14245645

my main source of confusion is what if it fails for some n?

say you are proving something about the expression 1/(50-x)
and it works for x=1 and you show if it works for x=k it works for x=k+1

but of course it will "fail" for x=50 because the expression is undefined
but induction does not detect this right?

Anonymous

Anonymous Sat 19 Feb 2022 05:08:06 No.14244920 Report

Quoted By:

>>14244915
>say you are proving something about the expression 1/(50-x)
>and it works for x=1 and you show if it works for x=k it works for x=k+1
then you fucked up somewhere

Anonymous

Anonymous Sat 19 Feb 2022 05:30:21 No.14244971 Report

Quoted By: >>14244995

>>14244915
>say it works for x=1 and you show if it works for x=k it works for x=k+1
then it automatically works for all x>=1. end of story.
>but of course it will "fail" for x=50 because the expression is undefined
if you actually showed the case of n=1 and n= => n=x+1 this is logically impossible.

Anonymous

Anonymous Sat 19 Feb 2022 05:42:23 No.14244995 Report

Quoted By: >>14245009 >>14245020

>>14244971
You could have some expression that involves summing an infinite series, something like a fourier transform that might be correct to some arbitrary index in the series, but then goes radically off of the rails and even comes back at some other index in the series.

Anonymous

Anonymous Sat 19 Feb 2022 05:47:40 No.14245009 Report

Quoted By: >>14245177

>>14244995
you wouldn't be able to prove anything about it which works for x=1 and if it works for x=k it works for x=k+1
But I'm just a simple country farmer, you should really try and find a property that works like that

Anonymous

Anonymous Sat 19 Feb 2022 05:49:20 No.14245020 Report

Quoted By:

>>14244995
No, you couldnt. What you are describing cannot happen. Feel free to prove me wrong.

Anonymous

Anonymous Sat 19 Feb 2022 07:06:16 No.14245177 Report

Quoted By: >>14245185 >>14248249

>>14245009
I mean it is pretty simple.
Suppose you had just a series
1, 2, 3, 4, ...
You just need some function which cancels itself out for various n, but not all n.
f(n) = g(n) + n | g(n_i) = 0 and g(n_i+1) = 0 and there is some g(n) ? 0
There are some obvious candidates such as a floor function which could immediately meet this criteria:
f(n) = floor(n/(n_i+2)) + n | n_i being constant here.
Another obvious one is a square wave function multiple.
$<br />f(n) = [P(sin(wn) + \frac{sin(3wn)}{3} + \frac{sin(5wn)}{5} + ... )+k]n + n<br />$
Here P, w, and k can be set to a number of things to adjust the cycle any direction we want.
For example P = -2/pi, w = pi - 2, k = 0.5
This will give a g(n) = 0 | n = 1, n = 2, but it will give g(n) = n | n = 3, n = 4

Anonymous

Anonymous Sat 19 Feb 2022 07:09:16 No.14245185 Report

Quoted By:

>>14245177
what statement will you prove about your function? If it's "g(n) = 0" I disagree that g(n) implies g(n+1)

Anonymous

Anonymous Sat 19 Feb 2022 11:17:08 No.14245513 Report

Quoted By:

>>14244657
That's not how induction works.
You start by proving the base case, starting proposition, then assume it is true for an arbitrary number, let's call it k, and then try and prove it is true for k+1 as well. If you can show that you can go from some arbitrary k to k+1, then this is proof you can do so for any greater number.

However, this is the simplest example of induction. It can get complicated if there is more than one case for different types of numbers, let's say for odd and even numbers. Then you'd have 2 base cases, and 2 proofs to show.
An odd k, to k+2.
And an even k, to k+2.

Anonymous

Anonymous Sat 19 Feb 2022 11:26:13 No.14245522 Report

Quoted By:

>>14244915
It would have to be something related to sequences and series where a value depends on the previous one.

A classic example is proving by induction that a sum of a series of numbers equals n*(n+1)/2
We define the range of it to be the natural numbers, making the base case 1.
Then, we pick an arbitrary k and assume the sum(1,k)=k*(k+1)/2

We determine our goal, which is to prove that sum(1, k+1) = (k+1)*(k+2)/2
Then we try and prove it for sum(1, k+1). We know that the sum of k+1 equals 1+2+3+4+...+k+(k+1)
And we use our assumptions for k here, so we get:
(1+2+3+4+...+k)+(k+1) = k*(k+1)/2 + (k+1) = ( k*(k+1)+2(k+1) )/2
Take our (k+1) as a common factor
(k+1)(k+2)/2

QED

Anonymous

Anonymous Sat 19 Feb 2022 11:26:40 No.14245524 Report

Quoted By:

>>14244657
Are you retarded? If you're talking about mathematical proof by induction, the point is to prove that if a proposition holds in one case, it necessarily holds in the subsequent case, no matter which two cases they are. If you then find a specific case where you can show that it does hold, you've proven rigorously that it holds in every subsequent case.

Anonymous

Anonymous Sat 19 Feb 2022 11:51:50 No.14245565 Report

Quoted By: >>14246744

The reason is simple. A million pixel side by side is a line even if they don't touch. The singular pixel is an axiom representing a singular. Yet nothing is actuality a singular. So the flaws are not the conclusion, but the initial axiom itself.

Anonymous

Anonymous Sat 19 Feb 2022 12:09:58 No.14245597 Report

Quoted By:

> Prove by induction that statement S_n is true for all positive integers n

You're proving two things:

>1. IF the statement is true for n=k THEN it is true for n=k+1 for an arbitrary k.

This tells you that if it is true for some k then it is also true for the next value and so on because you can just keep adding 1.

>2. The statement IS true for n=1

If you can show this then you know from the previous fact that it must be true for all natural numbers. You know it's true for 1 so it must be true for 2, you now know it's true for 2 so it must be true for 3 etc.

Maybe you can't prove it's true for 1 but you can prove it's true for 5 so then you would know it is true for 5 and above.

This is the base case.

>"What if it is true normally but untrue for some unknown value n=m?"

Then either you will be unable to prove the first fact because then "k true implies k+1 true" will not hold for k=m-1 OR if you can prove the first statement the lowest base case you can prove will be larger than m.

Anonymous

View Same Google iqdb SauceNAO Untitled.png, 43KiB, 1613x1210

Anonymous Sat 19 Feb 2022 12:39:38 No.14245645 Report

Quoted By: >>14245682

>>14244657
When using inductions you need to show two things.
1. The statement is true for a specific case (the base case)
2. If the statement is true for the nth case, it's true for the (n+1)th case.

By showing it's true for the first case (which you know it is, because that's what you did in (1)) You know it's true for the second case. (thanks to (2))
It being true for the second case means it's true for the third case, which means it's true for the fourth case and so on.

>>14244915
Let's assume you've proved the two requirement for induction mentioned above.
If the statement is false for some arbitrary value n than it can't be true for n-1, because if n-1 were true it would necessarily be true for n.
If it's not true for n-1 it's not true for n-2, which means it's not true for n-3 and so on until you find the statement is wrong for your base case, which supposedly you've proven.
If you get stuck in this position it means that either the statement isn't true or you fucked up a proof somewhere.

Induction helps you prove that something is true for a base case at the index $b\in\mathbb{N}$ and for every $n\in\mathbb{N}$ such that $n>b$ .
If at some arbitrary point it stops working than a proof by induction would fail.

Anonymous

Anonymous Sat 19 Feb 2022 13:06:07 No.14245682 Report

Quoted By: >>14245942 >>14249291

>>14245645
>If the statement is false for some arbitrary value n
I never said it would be FALSE
I said it would be UNDEFINED

Anonymous

Anonymous Sat 19 Feb 2022 14:58:49 No.14245923 Report

Quoted By: >>14247715

>>14244657
You don't actually need to assume anything, you can just show that P(n) -> P(n+1). Filtered.

Anonymous

Anonymous Sat 19 Feb 2022 15:03:45 No.14245942 Report

Quoted By: >>14248059

>>14245682
Give an example of a statement about an undefined expression that isn't false.

Anonymous

Anonymous Sat 19 Feb 2022 15:09:05 No.14245958 Report

Quoted By:

>>14244657
When the mathematicians say something like "assume it is true for n=k, we will show that this implies it is true for n=k+1" or whatever, what they're really saying is "we will prove that P(n) -> P(n+1)" so there is no assumption going on its just a proof of an implication.

Anonymous

Anonymous Sat 19 Feb 2022 16:36:23 No.14246171 Report

Quoted By:

>>14244657
it's like sticking one pillar into a foundation and seeing it stays put, and concluding that other pillars will behave the same in the same foundation

Anonymous

Anonymous Sat 19 Feb 2022 19:50:34 No.14246724 Report

Quoted By:

Congratulations on not understanding mathematical induction, anon!

Anonymous

Anonymous Sat 19 Feb 2022 19:54:52 No.14246744 Report

Quoted By:

>>14245565
based authentic schizophrenia sufferer

Anonymous

Anonymous Sat 19 Feb 2022 22:39:00 No.14247445 Report

Quoted By:

>>14244657
If a property holds for $k+1$ when it holds for $k$ and it holds for the initial case $k_0$ , then by implication it holds for
$k_1=k_0+1$ , $k_2=k_1+1= (k_0+1 )+1 =k_0 +2$ and so on so that it holds for all cases $k_n = k_0 + n$ .

Anonymous

Anonymous Sat 19 Feb 2022 22:45:20 No.14247471 Report

Quoted By:

>>14244657
How is it possible to not understand induction?
The point isn't to assume something is correct in a circular manner. The point is applying this presumption and seeing how far you can take it until there is a contradiction. If there isn't any, then that is a necessary (but not necessarily sufficient) condition that it holds generally.
You even used an illustration but still don't get it.

Anonymous

Anonymous Sat 19 Feb 2022 23:47:59 No.14247715 Report

Quoted By:

>>14244657
>>14244670
>>14244677
>>14244741
>>14245923

Let's rephrase this, so that retarded OP can undertand it. Induction is typically used for proofs over the natural numbers. We use the well ordering of the natural numbers to prove whatever we want to prove. The natural numbers are constructed using the peano axioms. We use the "axiom of induction" for our proof. First, we make sure our problem works for out first case, the base case. Then we show, that if our theorem holds for n it also holds for n+1. So we just ASSUME it works for n. But because we checked the base case, this implies should the base case be true, that it also holds for the successor of the base case and since this is true, the successor of this is true as well. Thus, we showed it's true for all n greater or eaqul to the base case

Anonymous

Anonymous Sun 20 Feb 2022 01:45:26 No.14248059 Report

Quoted By:

>>14245942
I think an issue is you are asking for a counterexample
when what is required is to somehow prove that there are not inputs for which induction fails for e.g. technical reasons like dividing by zero (or other more esoteric technical reasons).

Anonymous

Anonymous Sun 20 Feb 2022 03:25:30 No.14248249 Report

Quoted By: >>14248447

>>14245177
but isn't "it doesn't work for 50" a contradiction for "if it works for x, it works for x+1" because it works for 49, and 50 is 49+1? The conclusion that "if it works for x, it works for x+1" must have been a mistake, even if a small one.

Anonymous

Anonymous Sun 20 Feb 2022 05:03:41 No.14248447 Report

Quoted By:

>>14248249
precisely. anon is very dense and this part isn't clicking for some reason.

Anonymous

Anonymous Sun 20 Feb 2022 14:04:35 No.14249291 Report

Quoted By:

>>14245682
Let's go with the following example:
$\mathbb{Q}={\frac{z}{n} | z\in\mathbb{Z}, n\in\mathbb{N}}$
For clarification, $0\not{\in}\mathbb{N}$ .
The statement we want to prove or disprove is $\forall n \in \mathbb{N} \Rightarrow \frac{1}{80-n} \in \mathbb{Q}$

Of course we know that for n=80 the undefined value won't be in $\mathbb{Q}$ , but let's try to "prove" it with induction.

>Base:
for n=1 we know that $\frac{1}{80-1}=\frac{1}{79}\in\mathbb{Q}$
So we've proven the base case to be true.

>Step:
Let's assume the statement is true for n.
That is, $\frac{1}{80-n}\in\mathbb{Q}$
Let's show that from that follows that $\frac{1}{80-n-1}\in\mathbb{Q}$
$(80-(n+1)=80-n-1)$

To show that $\frac{z}{n}$ is in $\mathbb{Q}$ we need to show that $(z\in\mathbb{Z})\wedge(n\in\mathbb{N})$ .
We know that $1\in\mathbb{Z}$ , so now we need to show that if $(80-n)\in\mathbb{N}$ for a given n than it follows that $(80-n-1)\in\mathbb{N}$ .

$80-n\in\mathbb{N} \rightarrow 80-n\geq1 \rightarrow 79\geq n$
So if $(80-n)\in\mathbb{N}$ it follows that $79\geq n$ .

If I were thorough I'd also show that this statement is true for n>80 as well, but I'm lazy and running out of characters.
In retrospect I should have shown that { $\frac{z}{n} | n\in\mathbb{N}, z\in\mathbb{Z}$ } = { $\frac{z}{n} | z\in\mathbb{Z}, n\in\mathbb{Z}\setminus(0)$ }, but fuck it, let's pretend I did.

So we know this statement is true when $79\geq n$ or $n>81$ , let's assign n=79.
for n=79 we see that $80-79=1\in\mathbb{Z}\setminus (0)$ and therefor $\frac{1}{80-79}\in\mathbb{Q}$ .
However, $80-(79+1)=80-80=0 \not{\in}\mathbb{Z}\setminus 0$ , and therefor $\frac{1}{80-80} \not{\in} \mathbb{Q}$

And indeed we've shown a contradiction.

Capcode	All Only User Posts Only Moderator Posts Only Admin Posts Only Developer Posts
Show Posts	All Only With Images Only Without Images
Deleted Posts	All Only Deleted Posts Only Non-Deleted Posts
Ghost Posts	All Only Ghost Posts Only Non-Ghost Posts
Post Type	All Only Sticky Threads Only Opening Posts Only Reply Posts
Results	All Grouped By Threads
Order	Latest Posts First Oldest Posts First

Your latest searches