Thread: Induction and Reccurence Help Plz :(

1. Induction and Reccurence Help Plz :(

Induction Question:

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)?
HALP PLZ!

Recurrence:

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.

2. 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.