discrete math:functions,recurrence relation

Printable View

Mar 16th 2008, 11:31 PM
mahu and liz

discrete math:functions,recurrence relation

a) Let f:N*N->Q be defined by f(m,n)=(m-3)/n. Determine if f is injective or surjective.

b) Show that if f:A->B and g:B->C are both bijective, then the composition (g o f):A->c is also bijective.

Solve the recurrence relations

a(r)-5a(r-1)+6a(r-2)=2^r+r
(r,r-1,r-2 are all subscripts)
Mar 17th 2008, 04:27 AM
mr fantastic

Quote:

Originally Posted by mahu and liz

[snip]
Solve the recurrence relations

a(r)-5a(r-1)+6a(r-2)=2^r+r
(r,r-1,r-2 are all subscripts)

First solve the homogeneous recurrence relation $a_r - 5 a_{r-1} + 6 a_{r-2} = 0$ by assuming a solution of the form $A \lambda^r$ :

$a_r = A_1 2^r + A_2 3^r$ .

Now get particular solutions to the non-homogeneous recurrence relations:

1. $a_r - 5 a_{r-1} + 6 a_{r-2} = r$ : Try $a_r = \alpha + \beta r$ and solve for $\alpha$ and $\beta$ .

2. $a_r - 5 a_{r-1} + 6 a_{r-2} = 2^r$ : Note that $a_r = k 2^r$ is one of the homogeneous solutions. Therefore try $a_r = k r 2^r$ and solve for k.

Now add these two particular solutions to the homogeneous solution to get the general solution.
Mar 17th 2008, 10:14 PM
mahu and liz

boy ain't yu a guuuud

in kenya,we say "shukrani sana"-thank's alot.continue being good
Mar 18th 2008, 01:49 AM
mr fantastic

Quote:

Originally Posted by mr fantastic

First solve the homogeneous recurrence relation $a_r - 5 a_{r-1} + 6 a_{r-2} = 0$ by assuming a solution of the form $A \lambda^r$ :

$a_r = A_1 2^r + A_2 3^r$ .

Now get particular solutions to the non-homogeneous recurrence relations:

1. $a_r - 5 a_{r-1} + 6 a_{r-2} = r$ : Try $a_r = \alpha + \beta r$ and solve for $\alpha$ and $\beta$ .

2. $a_r - 5 a_{r-1} + 6 a_{r-2} = 2^r$ : Note that $a_r = k 2^r$ is one of the homogeneous solutions. Therefore try $a_r = k r 2^r$ and solve for k.

Now add these two particular solutions to the homogeneous solution to get the general solution.

Quote:

Originally Posted by mahu and liz in a pm

i still don't seem to find the a way of getting the answer.i have tried using your help but it reaches a part where P = 1/(2r-7) when i equated f(r)= 2^rthe second part where i am supposed to equate f(r)= r, am getting confused and ending up with a solution like 2*alpha+beta(2r-7)=r then another qs,where do you get this mathematical signs from.........alpha beta and the like you are highly appreciated

$a_r = \alpha + \beta r$

$\Rightarrow \alpha + \beta r - 5(\alpha + \beta [r-1] ) + 6(\alpha+ \beta [r-2] ) = r$

$\Rightarrow (\alpha - 5 \alpha + 5 \beta + 6 \alpha - 12 \beta) + r (\beta - 5 \beta + 6 \beta) = r$

$\Rightarrow (2 \alpha - 7 \beta ) + (2 \beta) r = r$ .

Equate coefficient of r on each side: $2 \beta = 1 \Rightarrow \beta = \frac{1}{2}$ .

Equate constant term on each side: $2 \alpha - 7 \beta = 0 \Rightarrow \alpha = \frac{7 \beta}{2} = \frac{7}{4}$ .

$a_r = k r \cdot 2^r$

$\Rightarrow k r \cdot 2^r - 5 k (r - 1) \cdot 2^{r-1} + 6 k (r - 2) \cdot 2^{r - 2} = 2^r$

Divide both sides by $2^{r-2}$ :

$\Rightarrow k r \cdot 2^2 - 5 k (r - 1) \cdot 2^1 + 6k (r - 2) = 2^2$

$\Rightarrow 4k r - 10 k r + 10 k + 6k r - 12 k = 4$

$\Rightarrow -2k = 4 \Rightarrow k = -2$ .

I reserve the right for this post to contain careless errors whihc will be easily spotted and fixed.