1. ## 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)

2. 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 $\displaystyle a_r - 5 a_{r-1} + 6 a_{r-2} = 0$ by assuming a solution of the form $\displaystyle A \lambda^r$:

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

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

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

2. $\displaystyle a_r - 5 a_{r-1} + 6 a_{r-2} = 2^r$: Note that $\displaystyle a_r = k 2^r$ is one of the homogeneous solutions. Therefore try $\displaystyle 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.

3. ## boy ain't yu a guuuud

in kenya,we say "shukrani sana"-thank's alot.continue being good

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

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

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

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

2. $\displaystyle a_r - 5 a_{r-1} + 6 a_{r-2} = 2^r$: Note that $\displaystyle a_r = k 2^r$ is one of the homogeneous solutions. Therefore try $\displaystyle 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.
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
$\displaystyle a_r = \alpha + \beta r$

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

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

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

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

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

$\displaystyle a_r = k r \cdot 2^r$

$\displaystyle \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 $\displaystyle 2^{r-2}$:

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

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

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

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