Sets

Obeng · 2013-09-21 11:43:16

Can someone please solve the following questions with detailed explanations for me? we are to discuss it before being taught, thank you.

Question 1
Show by mathematical induction that for all n ≥ 1 , 1+2 +3+..+n = (n(n+1))/2

Question 2
Evaluate the sum 1^2+2^2+3^2+..+r^2 by using the generating function 1/((1-z)) =1+z+z^2+z^3+z^4+z^r+

Question 3
Let A= { a,b,c,d,e } and R be a relation on set A such that M_R is given as :
Mr 10010
01000
00011
10000
01001

Find the transitive value of r using Warshall's theory

Question 4
In finite poset S,show that there is always at least one maximal element and one minimal element.

Question 5
Solve the recurrence equation a_n-a_(n-1)-a_(-2) =2n with a_0=0 and a_1=1

Any help is deeply appreciated

Bob · 2013-09-21 19:59:53

hi Obeng

Welcome to the forum. I may be able to help with some of these.

Q1 Induction means you need to show that the formula works for (say) n = 1. That should be straight forward for you.

Then you assume the formula is correct for n, and add the next term, working the algebra to show that what you now have is the same formula, but with all the terms with n, becoming n+1 instead.

So the first and last steps are:

add next term

Now, your turn. Factorise the common factor, put all over 2, and simplify.

Your target is:

Q5. Just checking I have the equation correct. Is it:

That means that

and

and so on down to

So you should be able to make a_n the subject and keep substituting the other terms until you have just a formula in 'n'.

OR

Now I look at what I've said so far, it might be easier to start with a_2 and work out its value, using this to work out a_3 and so on. It may then be obvious what the formula for a_n is.

I've had a little play with my last suggestion, and the formula for this is not going to be easy to find. Is that what 'solve' means here or will it be sufficient to generate the sequence?

Bob

bobbym · 2013-09-21 22:13:36

Hi;

Question 5
Solve the recurrence equation a_n-a_(n-1)-a_(-2) =2n with a_0=0 and a_1=1

Your recurrence is incorrect.

If you mean

a[n] - a[n - 1] - a[n - 2] = 2 n

with

a[0] == 0 , a[1] == 1

you can solve by using the auxiliary polynomial for the homogenous case and then adjusting for the 2n.

The answers will be long and difficult by hand. Please provide the correct recurrence.

Question 2
Evaluate the sum 1^2+2^2+3^2+..+r^2 by using the generating function 1/((1-z)) =1+z+z^2+z^3+z^4+z^r+

The technique is to build up from G(z) = 1 /(1-z) by using differentiation, integration and the shift operator. So far this has led to a generating function that I can not solve for. Is it possible to use a DE here?

gAr · 2013-09-21 23:05:30

Hi Obeng,

Q2.

Differentiate and multiply by z, twice, to get the g.f for <1^2, 2^2, 3^2...>
To get the sum, multiply by 1/(1-z)
Then get the partial fractions.

[z^n] is

Obeng · 2013-09-24 03:59:05

Thanks a lot bob bundy, bobbym I would very much appreciate if I could attach the assignment because the values and symbols get contorted if I paste it, thanks anyway, thanks gAR wow, I need more questions to practice before my exams, thanks u all, you guys are genius.

bobbym · 2013-09-24 04:13:12

Hi;

bobbym I would very much appreciate if I could attach the assignment because the values and symbols get contorted if I paste it

Math is presented in latex. Cutting and pasting will not work in most cases unless you are using a program that understands latex. Why not try a screenshot instead?

What about the recurrence?

anonimnystefy · 2013-09-24 06:45:52

Hi demha

Q4: Look at some number from the set x0. If it is the maximum, we are done. If not, there is a number x1, such that x1 is different from x0, which might be the maximum. If it is, again, we are done, if not, there is an element x2, for which the same properties hold. If we now assume that there is no maximum element, it would be true that there is an infinite series of elements of the poset x1, x2, x3, x4,...for which it is true that x1<=x2<=... which is impossible, because there is an finite number of elements in the poset.

Obeng · 2013-09-24 22:07:16

Please here are the screenshots of the questions, thanks a lot
https://www.dropbox.com/s/ukmeczmf8r889vb/discreteMaths.JPG
https://www.dropbox.com/s/6qjbadr9fo9i8g6/discreteMaths5.JPG

Last edited by Obeng (2013-09-24 22:14:47)

bobbym · 2013-09-24 22:13:14

I am not getting either of those links?!

Obeng · 2013-09-25 02:44:49

You can now check the link again ... Thank you for everything

bobbym · 2013-09-25 03:14:18

Hi;

What text is that from?

Math Is Fun Forum

#1 2013-09-21 11:43:16

Sets

#2 2013-09-21 19:59:53

Re: Sets

#3 2013-09-21 22:13:36

Re: Sets

#4 2013-09-21 23:05:30

Re: Sets

#5 2013-09-24 03:59:05

Re: Sets

#6 2013-09-24 04:13:12

Re: Sets

#7 2013-09-24 06:45:52

Re: Sets

#8 2013-09-24 22:07:16

Re: Sets

#9 2013-09-24 22:13:14

Re: Sets

#10 2013-09-25 02:44:49

Re: Sets

#11 2013-09-25 03:14:18

Re: Sets

Board footer