# Thread: phylosophy problem - proveing strategy

1. ## phylosophy problem - proveing strategy

Hi,

I am reading this book and there is an attempt to prove a concept by describin it and it is pretty vague what technique the writter is using to prove it. I mannaged to break his "proof" into variables and statements. so i have 4 variables

$\displaystyle y_{c}, x_{c}, k, c$

and the statemant the author is trying to prove is

$\displaystyle \forall x_{c} \in Z_{+}, y_{c} \geq x_{c}-k+1$

the tricky part is that it appears the following statements hold
$\displaystyle c>0, y_{c} =c$

$\displaystyle c=1, x_{c} = c+k+1$
and
$\displaystyle c>1, x_{c-1} +k +1\geq x_{c}\geq x_{c-1}$
but are not given in his formulation of what i call " his lemma".

so since i am new to discrete math, then if there is no clear formulation of the problem i don't know what strategy should i choose to prove the statement, i need some help.

my question is : To prove the statement, should i break it into cases? or is this a clasical case where one shoul use induction and treat c=1 as base case ? but what is the induction hypothesis then?. And how, one should formulate the statement correctly if one know the above stated facts.

As you can see I am confused. I would love to post the original text but it is in Macedonian and it is about the beauty of the mountain. so i doubt that anyone would invest his/hers time to break it into pieces and mess with it.

baxy

2. ## Re: phylosophy problem - proveing strategy

Originally Posted by baxy77bax
Hi,

I am reading this book and there is an attempt to prove a concept by describin it and it is pretty vague what technique the writter is using to prove it. I mannaged to break his "proof" into variables and statements. so i have 4 variables

$\displaystyle y_{c}, x_{c}, k, c$

and the statemant the author is trying to prove is

$\displaystyle \forall x_{c} \in Z_{+}, y_{c} \geq x_{c}-k+1$
??? That is NOT a "provable statement" because you have not said what $\displaystyle y_c$ is. Did you

the tricky part is that it appears the following statements hold
$\displaystyle c>0, y_{c} =c-k+1$
$\displaystyle c=1, x_{c} = c-k+1$
and
$\displaystyle c>1, x_{c-1} -k +1\geq x_{c}\geq x_{c-1}$
but are not given in his formulation of what i call " his lemma".

so since i am new to discrete math, then if there is no clear formulation of the problem i don't know what strategy should i choose to prove the statement, i need some help.

my question is : To prove the statement, should i break it into cases? or is this a clasical case where one shoul use induction and treat c=1 as base case ? but what is the induction hypothesis then?. And how, one should formulate the statement correctly if one know the above stated facts.

As you can see I am confused. I would love to post the original text but it is in Macedonian and it is about the beauty of the mountain. so i doubt that anyone would invest his/hers time to break it into pieces and mess with it.

baxy[/QUOTE]
The first thing you need to do is specify the statement to be proven more clearly. Was there no condition on "$\displaystyle y_c$"?

3. ## Re: phylosophy problem - proveing strategy

Yes, induction would be easiest.

You write $\displaystyle c=1, x_c = c+k+1$. This can be simplified further: $\displaystyle x_1 = 2+k$.

So, you want to show the base case (when $\displaystyle c=1$) that $\displaystyle y_1 \ge x_1-k+1 = 2+k-k+1 = 3$, so this fails for $\displaystyle c=1$. Let's change $\displaystyle x_1$. If $\displaystyle x_1=k$, then $\displaystyle y_1=1 \ge x_1-k+1 = k-k+1=1$ is true.

So, assume $\displaystyle y_c \ge x_c-k+1$ for some positive integer $\displaystyle c$. Then, you want to show $\displaystyle y_{c+1} \ge x_{c+1}-k+1$. Since $\displaystyle x_c \le x_{c+1} \le x_c+k+1$, you know that $\displaystyle x_{c+1}-k+1 \le x_c+k+1-k+1 = (x_c-k+1)+k+1 \le y_c+k+1 = y_{c+1}+k$. So, if $\displaystyle k>0$ and $\displaystyle x_{c+1} = x_c+k+1$, then again, this fails.

So, start very plainly with what you are trying to prove. So far, what you have stated cannot be proven.