Induction and Reccurence Help Plz :(
Prove by Induction that 2log(n!) > nlog(n) (n>2, n is an integer)
This question, I don't know how to link the assumed case to the inductive case, see the following:
Base Case: n = 3
2log(6) > 3log(3) is true (by using calc)
Assumed Case: n = k
2log(k!) > klog(k)
Inductive Case: n = k+1
2log(k+1) + 2log(k!) > (k+1)log(k+1)
From here I don't know what to do, I mean 2log(k!) is there, but klog(k)?
I never understood how to do complicated recurrence problems... e.g. Fibonacci series and all...
1. Solve x(n) = x(n-1) - (1/4)x(n-2(, with x0 = 1 and x1 = 1/2 (note that the (expression) are the subscripts)
2. Solve T(1) = 1, and for all n>=2, T(n) = 3T(n-1) + 2
I've been trying to do these questions (these are not the only ones) for hours and I just can't get forward with these 3 questions, so halp! Other ones, I was able to do.
Re: Induction and Reccurence Help Plz :(
Concerning the first problem, it's relatively easy to show that log(n * (n - k)) >= log n for k = 0, ..., n - 1.
Concerning the recurrence relation, look for a solution in the form x(n) = x^n.