Use induction to show that $f(n)=2\log_2n+1$

Question

Given is that $$f_n=f_{n/2}+2$$

$n=2^k$

$k=1,2,3...$

and $f(1)=1$

use induction to show that $f(n)=2\log_2n+1$

how do i use induction to solve this?

Answer 1

Note that since $n = {2^k}$, we should use induction in this much restricted space. First of all according to your recursive rule and initial condition for $f$, we have $$f(2) = f(1) + 2 = 3$$, also note that $$f({2^1}) = 2{\log _2}2 + 1 = 3$$so that the relation is true for the initial seed ($k=1$). Now, assume that the relation is also correct for some $k$, that is assume that $$f({2^k}) = 2{\log _2}{2^k} + 1 = 2k + 1$$now, for $k+1$ according to the recursive relation, we have $$f({2^{k + 1}}) = f({2^k}) + 2 = 2k + 3$$also, $$2{\log _2}{2^{k + 1}} + 2 = 2k + 3$$so that the identity is valid.

Answer 2

1) $f(1) = 1$

2) assume $f(n=2^k) = 2 \log_2 n + 1$

3) we need to prove that for $n' = 2^{k+1} = 2n$ it is true that $f(n') = 2 \log_2 n' + 1$. We know that $f_n = f_{n/2}+2$, hence $f_{n'} = f_{n'/2}+2 = f_{n}+2$, plug our assumption from part 2) here and get the result: $f_{n'} = 2 \log_2 n + 1 + 2 = 2(\log_2 n + 1) + 1= 2(\log_2 n + \log_2 2) + 1 = 2 \log_2 2n + 1 = 2 \log_2 n' + 1$.