if f(1)=1 and f(n+1)=2f(n)+1, if n>=1 then f(n)=

if i put some values of n then i got the answer but is there is any independent way of finding the answer.

Printable View

- Jun 1st 2011, 08:57 AMayushdadhwalhow to find the function
if f(1)=1 and f(n+1)=2f(n)+1, if n>=1 then f(n)=

if i put some values of n then i got the answer but is there is any independent way of finding the answer. - Jun 1st 2011, 09:14 AMabhishekkgp
- Jun 1st 2011, 09:19 AMTheEmptySet
I am not sure how else to solve this problem but to use the guess that the solution is of the form

$\displaystyle f(n)=Ar^n$

If you plug this into the homogenous equation (get rid of the 1) we get

$\displaystyle r^n+1=2r^n \iff r^{n}(r-2)=0 \implies r=2$

Since the nonhomogenous term is a constant we guess that the particular solution is also a constant so we have that

$\displaystyle f(n)=A2^n+B$ if we plug this in we get

$\displaystyle A2^{n+1}+B=2(Ar^n+B)+1 \iff A2^{n+1}+B=A2^{n+1}+2B+1 \iff B=-1 $

So we get

$\displaystyle f(n)=A2^{n}-1$

Finally if we use the initial condition we get that

$\displaystyle f(1)=2A-1=1 \implies A=1$

$\displaystyle f(n)=2^{n}-1$