>>18
Huh? I have my undegrad data structures book right in front of me. This book, like most data structures books, takes a recursive function, then converts it to a recurrence relation. The proof of correctness is proving the recurrence relation by induction.
Again, you're stupid. And again, you have no possible future as a computer progrmmer.