# how to find the function

• Jun 1st 2011, 08:57 AM
how 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 AM
abhishekkgp
Quote:

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.

$f(2)=2f(1)+1$
$f(3)=2f(2)+1$
.
.
.
$f(n+1)=2f(n)+1$.
multiply the second last equation by 2, the third last equation by 4 , the fourth last equation by 8 and so on... then add all the equations.
• Jun 1st 2011, 09:19 AM
TheEmptySet
I am not sure how else to solve this problem but to use the guess that the solution is of the form

$f(n)=Ar^n$

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

$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

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

$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

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

Finally if we use the initial condition we get that

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

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