OK. I think I have it. So what I ended up doing was brute forcing a base case of ##0 \le n \le 2## and testing it for 0, 1, and 2 (which holds). Then I showed that for all ##k \ge 2##
##3^{k+1} = 3*3^k##
##2^{k+1} = 2*2^k##
##k+1 \le (1.5)k##
This got me to derive ##3^{k+1} \ge (k+1)2^{k+1}...
Heh. I'm following as best I can I really don't follow. :P I can't see how ∃ 3^{k+1} ≤ (k+1)2^{k+1} is any easier to disprove than ∀ 3^{k+1} ≥ (k+1)2^{k+1} is to prove.
I think I've explained my steps a little wrong. The first thing I did after the base case was assume 3^k≥k2^k
Then I setup 3^{k+1}=3(3k)≥3(k2^k)≥...
But I simply cannot find something to substitute ... that is actually true
Homework Statement
The question asks me to prove inductively that 3n ≥ n2n for all n ≥ 0.
Homework EquationsThe Attempt at a Solution
I believe the base case is when n = 0, in which case this is true. However, I cannot for the life of me prove n = k+1 when n=k is true. I start with:
3^k ≥...