Question

If $f:\mathbb{N}\to \mathbb{N}$be a function satisfying the functional equation f(1) = 1 and f(n+1) = 2f(n) + 1 $n\ge 1$, then f(n) is
[a] ${{2}^{n+1}}$
[b] ${{2}^{n}}$
[c] ${{2}^{n}}-1$
[d] ${{2}^{n-1}}-1$

Answer 1

Hint: Express f(n) in terms of f(n-1). Again using the functional equation, express f(n-1) in terms of f(n-2). Hence express f(n) in terms of f(n-2). Continuing this way, express f(n) in terms of f(1). Use f(1) = 1 and hence find the expression for f(n). Verify your answer.

Complete step-by-step answer:
We have
f(n+1) =2 f(n)+1
Replacing n by n-1, we get
f(n) = 2f(n-1)+1
Replacing n by n-2 in the functional equation, we get
f(n-1) =2f(n-2)+1
Substituting the value of f(n-1) in the expression of f(n), we get
f(n) =2(2f(n-2)+1)+1
i.e. $f\left( n \right)={{2}^{2}}f\left( n-2 \right)+\left( 1+2 \right)$
Replacing n by n-3 in the functional equation, we get
f(n-2) = 2f(n-3)+1
Substituting the value of f(n-2) in the expression of f(n), we get
$f\left( n \right)={{2}^{2}}\left( 2f\left( n-3 \right)+1 \right)+\left( 1+2 \right)={{2}^{3}}f\left( n-3 \right)+\left( 1+2+{{2}^{2}} \right)$
Hence, we have
$f\left( n \right)={{2}^{k}}f\left( n-k \right)+\left( 1+2+{{2}^{2}}+\cdots +{{2}^{k-1}} \right)$
Hence, we have
$f\left( n \right)={{2}^{n-1}}f\left( n-\left( n-1 \right) \right)+\left( 1+2+{{2}^{2}}+\cdots +{{2}^{n-2}} \right)={{2}^{n-1}}f\left( 1 \right)+\left( 1+2+{{2}^{2}}+\cdots +{{2}^{n-2}} \right)$
We know that f(1) = 1. Hence, we have
$f\left( n \right)={{2}^{n-1}}+\left( 1+2+{{2}^{2}}+\cdots +{{2}^{n-2}} \right)$
Now consider the series $1+2+{{2}^{2}}+\cdots +{{2}^{n-2}}$
Clearly, the series is geometric series with the first term as 1, common difference as 2 and the number of terms as n-1
We know that in geometric series ${{S}_{n}}=\dfrac{a\left( {{r}^{n}}-1 \right)}{r-1}$
Hence, we have
$1+2+{{2}^{2}}+\cdots +{{2}^{n-2}}=\dfrac{1\left( {{2}^{n-1}}-1 \right)}{2-1}={{2}^{n-1}}-1$
Hence, we have
$f\left( n \right)={{2}^{n-1}}+{{2}^{n-1}}-1=2\left( {{2}^{n-1}} \right)-1={{2}^{n}}-1$
Hence option [c] is correct.

Note: Verification
We have
$f\left( n+1 \right)={{2}^{n+1}}-1$ and $f\left( n \right)={{2}^{n}}-1$
Hene, we have
$f\left( n+1 \right)-2f\left( n \right)={{2}^{n+1}}-1-\left( 2 \right)\left( {{2}^{n}}-1 \right)={{2}^{n+1}}-1-{{2}^{n+1}}+2=1$
Hence, we have
$f\left( n+1 \right)=2f\left( n \right)+1$
Also, we have
$f\left( 1 \right)={{2}^{1}}-1=1$
Hence our answer is verified to be correct.