 #1
 8
 1
Homework Statement:

Suppose f(n) is a function that accepts an integer n as a parameter. When called with n = 1, it executes 2 instructions. When called with a larger value of n, it executes 10n + 30 instructions, two of which are f(n/2). Prove that f(n) executes 10n lg n + 32n − 30 instructions for all n ≥ 1.
lg = log base 2. Hint: a useful property of logs is that lg(a/b) = lg(a)  lg(b) for any nonzero a,b
Relevant Equations:
 ...
Homework Statement: Suppose f(n) is a function that accepts an integer n as a parameter. When called with n = 1, it executes 2 instructions. When called with a larger value of n, it executes 10n + 30 instructions, two of which are f(n/2). Prove that f(n) executes 10n lg n + 32n − 30 instructions for all n ≥ 1.
lg = log base 2. Hint: a useful property of logs is that lg(a/b) = lg(a)  lg(b) for any nonzero a,b
Homework Equations: ...
This is how far I get:
let n = k+1
instructions for f(k+1) = 10(k+1) + 30 + 10(k+1)/2 + 30 + 10(k+1)/2 + 30
= 10k + 10 + 30 + (10k+10)/2 + 30 + (10k+10)/2 + 30
= 10k + 10 + 30 + 10k + 10 + 30 + 30
then rearranging we get = (10k + 30) + (10K + 30) + 10 + 10 + 30
from inductive step we know (10k + 30) = (10k⋅lgk + 32k  30) therefore
= (10k⋅lgk + 32k  30) + (10k⋅lgk + 32k  30) + 10 + 10 + 30
I get stuck at this point
lg = log base 2. Hint: a useful property of logs is that lg(a/b) = lg(a)  lg(b) for any nonzero a,b
Homework Equations: ...
This is how far I get:
let n = k+1
instructions for f(k+1) = 10(k+1) + 30 + 10(k+1)/2 + 30 + 10(k+1)/2 + 30
= 10k + 10 + 30 + (10k+10)/2 + 30 + (10k+10)/2 + 30
= 10k + 10 + 30 + 10k + 10 + 30 + 30
then rearranging we get = (10k + 30) + (10K + 30) + 10 + 10 + 30
from inductive step we know (10k + 30) = (10k⋅lgk + 32k  30) therefore
= (10k⋅lgk + 32k  30) + (10k⋅lgk + 32k  30) + 10 + 10 + 30
I get stuck at this point