Originally posted by: raptor13
Originally posted by: z0mb13
Originally posted by: raptor13
You do mean that as log and not natural log, right? In either case, you first do the basis step by setting n = 1 and showing the statement is valid. Then you do the induction step by assuming the statement is true for some n, then substituting n + 1 for n, and showing the statement is still valid. By doing so, you've shown the statement is true for n and it implies the statement is true for n + 1 and thus is true for any number n.
That's induction for you.
oh yeah I remember this...
hm ok so the base case is EZ:
lg (n+1) <= 1 + lg(n)
lg((n+1)/n) <= 1
ln 2 <= 1
then the n+1 part kinda confuses me
lg((n+2)/(n+1)) <= 1
how do u do the induction from here?
You inserted n+1 properly but you're making the algebra much harder than it needs to be. After inserting n+1 but doing nothing else, you have:
log(n+2) <= 1 + log(n+1)
To rid yourself of the logs, take 10^(log(n+2)) <= 10^1 + 10^(log(n+1)) giving you:
n + 2 <= 10 + n + 1
Subtracting n from both sides, you have
2 <= 11
That is obviously always true and, since it is true for any and all n, the statement is valid for any n >= 1.
As I said, you can do the algebra your way by subtracting the log(n+1) and incorporting that into the log(n+2) term. Using partial fractions, you could rewrite it and solve it that way. Or you could take the limit at n->infinity. Taking the limit ruins the induction, however, though it would still weakly prove the statement.
Facebook
Twitter