Solveeit Logo
Login

Question

Question: If \(f:\mathbb{N}\to \mathbb{N}\)be a function satisfying the functional equation f(1) = 1 and f(n+1...

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

Explanation

Solution

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(n)=22f(n−2)+(1+2)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(n)=22(2f(n−3)+1)+(1+2)=23f(n−3)+(1+2+22)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(n)=2kf(n−k)+(1+2+22+⋯+2k−1)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(n)=2n−1f(n−(n−1))+(1+2+22+⋯+2n−2)=2n−1f(1)+(1+2+22+⋯+2n−2)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(n)=2n−1+(1+2+22+⋯+2n−2)f\left( n \right)={{2}^{n-1}}+\left( 1+2+{{2}^{2}}+\cdots +{{2}^{n-2}} \right)
Now consider the series 1+2+22+⋯+2n−21+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 Sn=a(rn−1)r−1{{S}_{n}}=\dfrac{a\left( {{r}^{n}}-1 \right)}{r-1}
Hence, we have
1+2+22+⋯+2n−2=1(2n−1−1)2−1=2n−1−11+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(n)=2n−1+2n−1−1=2(2n−1)−1=2n−1f\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(n+1)=2n+1−1f\left( n+1 \right)={{2}^{n+1}}-1 and f(n)=2n−1f\left( n \right)={{2}^{n}}-1
Hene, we have
f(n+1)−2f(n)=2n+1−1−(2)(2n−1)=2n+1−1−2n+1+2=1f\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(n+1)=2f(n)+1f\left( n+1 \right)=2f\left( n \right)+1
Also, we have
f(1)=21−1=1f\left( 1 \right)={{2}^{1}}-1=1
Hence our answer is verified to be correct.