You are not logged in.
Pages: 1
I've found two problems I do not really know how to solve... can you help me please?
the first one is about graph theory, and states that a simple graph has n vertices such that for any two distinct vertices x and y, the degree of x plus the degree of y is greater than or equal to n − 1 (symbolically, deg(x) + deg(y) ≥ n − 1). Does this guarantee that G will be connected? If yes, prove it.
the second is about Fibonacci numbers and recurrence relations, and requires to prove in a combinatorial way that for n ≥ 0, f(0) + f(1) + f(2) + ... + f(n) = f(n+2) − 1, where the f are the Fibonacci numbers, f(0)=1 and f(1)=1
thanks in advance
I'm not sure if this method counts as a combinatorial way, but you can prove the fibonacci one with induction fairly simply.
Base case:
n=0.
f(0+2)-1 = f(0)
2-1 = 1, so this is correct.
Induction case:
Assume that the statement is true for n=k.
ie. f(0)+...+f(k) = f(k+2)-1.
Now, f(k+3)-1 = f(k+1)+f(k+2)-1.
By the induction hypothesis, this is f(k+1) + [f(0)+...+f(k)-1] - 1.
So f(k+3)-1 = f(0)+...+f(k+1) - 1.
Therefore, the statement is true for all n.
Why did the vector cross the road?
It wanted to be normal.
Offline
For 1, assume that there are at least 2 unconnected parts of the graph, one having k vertices and the other having l. You should get a contradiction from this.
For 2, induction is not a combinatorial proof.
"In the real world, this would be a problem. But in mathematics, we can just define a place where this problem doesn't exist. So we'll go ahead and do that now..."
Offline
Fair enough. I don't see how combinatorics and Fibonacci are at all related though.
Why did the vector cross the road?
It wanted to be normal.
Offline
Wikipedia has the combinatorial proof of this result.
"In the real world, this would be a problem. But in mathematics, we can just define a place where this problem doesn't exist. So we'll go ahead and do that now..."
Offline
For 1, assume that there are at least 2 unconnected parts of the graph, one having k vertices and the other having l. You should get a contradiction from this.
Really? but how do you get up to the contradiction? that's what I cannot see...
If one "section" of the graph has k vertices, what's the maximum degree at any one of those vertices in that "section".
"In the real world, this would be a problem. But in mathematics, we can just define a place where this problem doesn't exist. So we'll go ahead and do that now..."
Offline
Pages: 1