Sup! We are currently talking about mathematical induction for Algorithms. And I honestly have no idea how it works. An example exercise we'd get is "Σn i = 1 log(i) = O(n log n)". And I have no idea how to solve it (or anything using mathematical induction)
#How does mathematical induction work?
royal vessel
royal vessel
Anyone? 👀
upper talon
"Σn i = 1 log(i) = O(n log n)"
this doesn't make much sense to me
can you write the exercise statement better?
severe bramble
ohhh is that big O notation?
ive heard of that but i dont know enough about it to help i think
upper talon
ohhh is that big O notation?
yes
so a function f is big O of another g at, say, infinity, iff
there exists a constand C > 0 such that
|f(x)| =< C|g(x)|
for every x >> 0 (for every x > A for some constant A)
in this case we're talking about sequences, so in this case we write the same as above with n in place of x
n ranging on positive integers
so for example,
sin(n) = O(1)
n^2 = O(e`n)
log(n) = O(n)
those last two aren't sharp estimates but they're true
so do you get what is to prove now?
royal vessel
so do you get what is to prove now?
But how does mathematical induction work
severe bramble
the method is show a base case then show step k implies step k+1
the idea is that if you have that thing implies thing after it is true and you show one thing is true, then we know the thing after that is true and so the thing after that is also true and so on
upper talon
yeah, I like to explain with the "infinite line of dominos analogy":
Imagine an infinite line of numbered dominos, starting with domino #1, then next is #2 and so on.
Induction tells you that: All dominos will fall if, and only if, the following two assertions are true:
- Domino #1 will fall;
- If a domino falls, the one right after it also falls.
Notice that the second assertion can also be written as
"For any positive integer n: If domino #n falls, then domino #(n+1) also falls."
Can you write explicitly what you need to prove and then do at least the base case of the induction now?