floor function

chrislav

New member
Joined
Jun 22, 2017
Messages
37
is it provable the following
[math]\lfloor x^n\rfloor\geq(\lfloor x\rfloor)^n[/math] for all naturals n and reals x
I can prove it for n=2,3,4
But i cannot generilised it to n
 

Dr.Peterson

Elite Member
Joined
Nov 12, 2017
Messages
12,647
is it provable the following
[math]\lfloor x^n\rfloor\geq(\lfloor x\rfloor)^n[/math] for all naturals n and reals x
I can prove it for n=2,3,4
But i cannot generilised it to n
Please show what you did -- you should know that by now!

It may be that we can help you generalize it. But we're not just going to do it for you.
 

chrislav

New member
Joined
Jun 22, 2017
Messages
37
Hint: it is provable;). Can you post you proof for n=3 and 4?

for n=3 we have:
Let x=n+a where n is a natural No and [math]0\leq a<1[/math]then:
[math]\lfloor(n^3+3n^2a+3na^2+a^3\rfloor\geq n^3\Leftrightarrow\lfloor(3n^2a+3na^2+a^3)\rfloor[/math][math]\Leftrightarrow(3n^2a+3na^2+a^3)\geq 0[/math]Now for a=0 we have [math]0\geq 0[/math] which is correct
For [math]a\neq 0[/math] we have:
[math](3n^2+3na+a^2)\geq 0[/math] which is correct
Hence :
[math]\lfloor x^3\rfloor\geq(\lfloor x\rfloor)^3[/math]
 

JeffM

Elite Member
Joined
Sep 14, 2012
Messages
6,963
is it provable the following
[math]\lfloor x^n\rfloor\geq(\lfloor x\rfloor)^n[/math] for all naturals n and reals x
I can prove it for n=2,3,4
But i cannot generilised it to n
I would definitely attack this one by cases. For one thing, I am not sure it is even true for negative x. (Not saying it is false; just saying it is not intuitively obvious to me that it is true for negative x.)

My first case would be the trivial one that n = 1.

My next case would be the trivial one that x is an integer.

[math]x \in \mathbb Z \implies (\lfloor x \rfloor = x \text { and } x^n \in \mathbb Z \implies[/math]
[math]\lfloor x^n \rfloor = x^n = (\lfloor x \rfloor)^n.[/math]
Then I would go for proofs by induction. Based on my first case, we can certainly say

[math]\exists \text { integer } k \ge 1 \text { such that } \lfloor x^k \rfloor \ge (\lfloor x \rfloor )^k \text { for non-integer } x > 0.[/math]
Now see what that entails for k + 1 given that

[math]\exists \text { integer } p \text { such that } 0 \le p < x < p + 1 \implies p^k < x^k < (p + 1)^k.[/math]
 

chrislav

New member
Joined
Jun 22, 2017
Messages
37
for n=3 we have:
Let x=n+a where n is a natural No and [math]0\leq a<1[/math]then:
[math]\lfloor(n^3+3n^2a+3na^2+a^3\rfloor\geq n^3\Leftrightarrow\lfloor(3n^2a+3na^2+a^3)\rfloor[/math][math]\Leftrightarrow(3n^2a+3na^2+a^3)\geq 0[/math]Now for a=0 we have [math]0\geq 0[/math] which is correct
For [math]a\neq 0[/math] we have:
[math](3n^2+3na+a^2)\geq 0[/math] which is correct
Hence :
[math]\lfloor x^3\rfloor\geq(\lfloor x\rfloor)^3[/math]
Sorry but there is a mistake here it should be;
for k=3 where k is natural No
and n should be an integer
 

chrislav

New member
Joined
Jun 22, 2017
Messages
37
I would definitely attack this one by cases. For one thing, I am not sure it is even true for negative x. (Not saying it is false; just saying it is not intuitively obvious to me that it is true for negative x.)

My first case would be the trivial one that n = 1.

My next case would be the trivial one that x is an integer.

[math]x \in \mathbb Z \implies (\lfloor x \rfloor = x \text { and } x^n \in \mathbb Z \implies[/math]
[math]\lfloor x^n \rfloor = x^n = (\lfloor x \rfloor)^n.[/math]
Then I would go for proofs by induction. Based on my first case, we can certainly say

[math]\exists \text { integer } k \ge 1 \text { such that } \lfloor x^k \rfloor \ge (\lfloor x \rfloor )^k \text { for non-integer } x > 0.[/math]
Now see what that entails for k + 1 given that

[math]\exists \text { integer } p \text { such that } 0 \le p < x < p + 1 \implies p^k < x^k < (p + 1)^k.[/math]
how do you know that if x belongs to integers then [math] x^n [/math] belongs to integers as well
 

JeffM

Elite Member
Joined
Sep 14, 2012
Messages
6,963
how do you know that if x belongs to integers then [math] x^n [/math] belongs to integers as well
Because the integers are closed with respect to multiplication: the product of integers is an integer.
 

Dr.Peterson

Elite Member
Joined
Nov 12, 2017
Messages
12,647
yes but how do know that holds for all n
That depends on what your starting point is in your class.

Presumably you are starting from some definitions and axioms, or perhaps they are just called properties. Closure may just be given, or might have been proved; but you wouldn't be assigned this proof without knowing that it is true.

Please tell us about your class, as well as why you aren't sure that the integers are closed with respect to multiplication.
 

JeffM

Elite Member
Joined
Sep 14, 2012
Messages
6,963
yes but how do know that holds for all n
This is the problem with questions about proofs. We do not know what axioms you start with and what theorems have already been proved prior to the specific theorem you are asking about.

In most courses, you are not expected to prove that the sum of two integers is itself an integer or that the product of two integers is itself an integer. Such propositions are treated as axioms along with commutivity and the distribution law. Your course probably starts by assuming that the integers have the properties of a commutative group with respect to addition and the properties of a commutative monoid with respect to multiplication.

In a foundations course, you might start with just the Peano postulates. In an abstract algebra course, you might start with the axioms and definitions of a semi-group.
 
Last edited:

chrislav

New member
Joined
Jun 22, 2017
Messages
37
That depends on what your starting point is in your class.

Presumably you are starting from some definitions and axioms, or perhaps they are just called properties. Closure may just be given, or might have been proved; but you wouldn't be assigned this proof without knowing that it is true.

Please tell us about your class, as well as why you aren't sure that the integers are closed with respect to multiplication.
my question was clear how do we know(prove) that [math] x^n[/math] belongs to integers for all n
given that x belongs to integers
I know about axioms theorems definitions and all that stuff.
In 1st order theories in any axiomatic development inclusion is not mentioned at all
But in other axiomatic developments some books use the inclusion property as an axiom
I do not belong to any class.
For example in any 1st order axiomatic development the following theorem substitutes the inclusion property
[math]\forall x\forall y\exists z![x+y=z][/math] for the operation of addition
or [math]\forall x\forall y\exists z![x.y=z][/math] for the operation of multiplication
In some other axiomatic formulations [math]\forall x\forall y\exists z![x+y=z][/math] is taken as an axiom.There is no need for it because informality says again that addition is a binary operation and formality says it can be proved.
But in our case we have not only two Nos but n Nos that cover an infinite amount of Nos and i wonder how can we prove that
By induction ,how?
This is the problem with questions about proofs. We do not know what axioms you start with and what theorems have already been proved prior to the specific theorem you are asking about.

In most courses, you are not expected to prove that the sum of two integers is itself an integer or that the product of two integers is itself an integer. Such propositions are treated as axioms along with commutivity and the distribution law. Your course probably starts by assuming that the integers have the properties of a commutative group with respect to addition and the properties of a commutative monoid with respect to multiplication.

In a foundations course, you might start with just the Peano postulates. In an abstract algebra course, you might start with the axioms and definitions of a semi-group.
 

JeffM

Elite Member
Joined
Sep 14, 2012
Messages
6,963
If you are merely wondering how to prove that [math]x^n[/math] is an integer given x is an integer and n is a non-negative integer, yes, it is a simple proof by mathematical induction..

[math]\text {Given } n \text { is an integer } \ge 0, \text { define }\\ x^n = 1 \text { if } n = 0;\\ x^n = x * x^{(n-1)} \text { if } n > 0.[/math]
[math]\text {Prove, given } x, \ n \in \mathbb Z \text { and } n \ge 0, \text { that } x^n \in \mathbb Z.[/math]
[math]n = 0 \implies x^n = 1 \in \mathbb Z.[/math]
[math]\therefore \exists \text { integer } k \ge 0 \text { such that } x^k \in \mathbb Z.[/math]
[math]\therefore k + 1 \text { is an integer} > 0 \implies x^{(k+1)} = x * x^{\{(k+1)-1\}} = x * x^k.[/math]
[math]x \text { and } x^k \text { are integers} \implies x * x^k \text { is an integer} \implies[/math]
[math]x^{(k+1)} \text { is an integer.}[/math]
 

chrislav

New member
Joined
Jun 22, 2017
Messages
37
If you are merely wondering how to prove that [math]x^n[/math] is an integer given x is an integer and n is a non-negative integer, yes, it is a simple proof by mathematical induction..

[math]\text {Given } n \text { is an integer } \ge 0, \text { define }\\ x^n = 1 \text { if } n = 0;\\ x^n = x * x^{(n-1)} \text { if } n > 0.[/math]
[math]\text {Prove, given } x, \ n \in \mathbb Z \text { and } n \ge 0, \text { that } x^n \in \mathbb Z.[/math]
[math]n = 0 \implies x^n = 1 \in \mathbb Z.[/math]
[math]\therefore \exists \text { integer } k \ge 0 \text { such that } x^k \in \mathbb Z.[/math]
[math]\therefore k + 1 \text { is an integer} > 0 \implies x^{(k+1)} = x * x^{\{(k+1)-1\}} = x * x^k.[/math]
[math]x \text { and } x^k \text { are integers} \implies x * x^k \text { is an integer} \implies[/math]
[math]x^{(k+1)} \text { is an integer.}[/math]
yes but behind every definition we must have a theorem of existence
For example behind the definition of sqrt we have a theorem of existence
behind the definition of logarith we have a theorem of existence e.t.c e.t.c
In our case what would be the theorem of existence for the definition you produced for the definition: [math]x^n=x.x^{n-1}[/math]?
 

pka

Elite Member
Joined
Jan 29, 2005
Messages
11,329
yes but behind every definition we must have a theorem of existence
For example behind the definition of sqrt we have a theorem of existence
behind the definition of logarith we have a theorem of existence e.t.c e.t.c
In our case what would be the theorem of existence for the definition you produced for the definition: [math]x^n=x.x^{n-1}[/math]?
Using the structure of the integers and the fact that if [imath]a\in\Re[/imath] then [imath]\exists! k\in \mathbb{N}[n\le a<k+1[/imath].
Your question about [imath]x=x\cdot x^{n-1}[/imath] does not need proof beyond the nature of operation on exponents.
But it is known and proven that there is no integer between [imath]k~\&~k+1[/imath] forall [imath]k\in\mathbb{N}[/imath].
Moreover, we know that [imath]\lfloor a \rfloor[/imath] is the largest integer that does not exceed [imath]a[/imath].
So that gives us [imath]\lfloor a \rfloor \le a<\lfloor a \rfloor +1[/imath] How know that [imath]\lfloor a^k \rfloor\le a^k<\lfloor a^k \rfloor+1~?[/imath] (do we even know that?)
[imath][/imath][imath][/imath][imath][/imath][imath][/imath][imath][/imath]
 

JeffM

Elite Member
Joined
Sep 14, 2012
Messages
6,963
yes but behind every definition we must have a theorem of existence
For example behind the definition of sqrt we have a theorem of existence
behind the definition of logarith we have a theorem of existence e.t.c e.t.c
In our case what would be the theorem of existence for the definition you produced for the definition: [math]x^n=x.x^{n-1}[/math]?
That is plain ridiculous. How can you possibly prove the existence of something that is not defined?
 
Top