# how to find the function

Printable View

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

Originally Posted by ayushdadhwal
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.

\$\displaystyle f(2)=2f(1)+1\$
\$\displaystyle f(3)=2f(2)+1\$
.
.
.
\$\displaystyle 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

\$\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\$