(adsbygoogle = window.adsbygoogle || []).push({}); 1. The problem statement, all variables and given/known data

f(n) = 0 when n=1 and 2f(n/2) + n - 1 when n is otherwise

2. Relevant equations

Repeated substitution

3. The attempt at a solution

f(n) = 2f(n/2) + n - 1

= 2^{2}f(n/2^{2}) + n - 3

= 2^{3}f(n/2^{3}) + n - 7

= 2^{4}f(n/2^{4}) + n - 15

Guess: f(n) = 2^{k}f(n/2^{k}) + n - (k-1)

we know from the recurrence that f(1) = 0, so need n/2^{k}= 0

so n/2^{k}=> n = 2^{k}=> lg n = k where lg is not log based 10 but log based 2

f(n) = 2^{lg n}f(n/2^{lg n}) + n - lg n + 1

when n = 1

f(n) = 2^{lg 1}f(n/2^{lg 1}) + 1 - lg 1 + 1 = 1f(1) + 1 + 0 + 1 = 2 so this recurrence cannot be proven,

**Physics Forums | Science Articles, Homework Help, Discussion**

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Homework Help: Repeated substitution help

**Physics Forums | Science Articles, Homework Help, Discussion**