# discrete math proofs

• December 13th 2005, 06:01 PM
innuenn
discrete math proofs
1.) If n is the element of natural numbers and n is a perfect square, then the units digit of n is not 2.

2.) If a,b is in the emement of natural numbers and both a and b are odd, then x^2+ax+b can not be factored into a product of two linear factors (a linear factor has the form cx+d, where c,d are elements of natural numbers)

3.) Prove by Induction
1+x+x^2+...+x^n=(x^(n+1)-1)/(x-1)
• December 14th 2005, 05:59 AM
CaptainBlack
Quote:

Originally Posted by innuenn
1.) If n is the element of natural numbers and n is a perfect square, then the units digit of n is not 2.

If $n$ is a perfect square there is a natural number $k$ such that $n=k^2$. Now write:

$k=t.10+u$,

where $0 \leq u \leq 9$ is the units digit of $k$ then

$k^2=100.t^2+20.t.u+u^2$.

So the units digit of $n$ is equal to the units digit of $u^2$.

Now look at the units digit of $u^2$ for $u=0,1,\ ..\ 9$ and you
will see if this ever is equal to $2$.

RonL
• December 14th 2005, 01:48 PM
CaptainBlack
Quote:

Originally Posted by innuenn
2.) If a,b is in the emement of natural numbers and both a and b are odd, then x^2+ax+b can not be factored into a product of two
linear factors (a linear factor has the form cx+d, where c,d are elements of natural numbers)

Suppose that $x^2+a.x+b$ with $a$ and $b$
odd, can be factored into a product of two
linear factors $c.x+d$ and $e.x+f$ with
$c,\ d,\ e,\ f$ all natural numbers. Then:

$x^2+a.x+b = (c.x+d)(e.x+f)$
$=c.e.x^2+(d.e+c.f).x+d.f$
.

Now equate coefficients of corresponding powers of x:

$c.e=1$

$d.e+c.f=a$

$d.f=b$

As $c$ and $e$ are natural numbers
the first of these equations implies $c=e=1$.
Substituting these into the second equation gives:

$d+f=a$

Now the third of these equations implies both $d$ and
$f$ are odd as by assumption $b$ is odd.
But $d$ and $f$ odd implies that their sum is
even, but by assumption $a$ is odd and is equal to the sum
of $d$ and $f$ which is even - a contradiction.

Hence $x^2+a.x+b$ with $a$ and $b$
odd natural numbres, cannot be factored into a product
of two such linear factors.

RonL
• December 14th 2005, 02:04 PM
innuenn
thanks for the help
• December 14th 2005, 03:37 PM
ThePerfectHacker
The answer to the last one, you can look up for a
finite geometric series.
• December 15th 2005, 12:08 AM
CaptainBlack
Quote:

Originally Posted by innuenn
3.) Prove by Induction
1+x+x^2+...+x^n=(x^(n+1)-1)/(x-1)

All inductive proofs have the same format.

We have a proposition $P(n)$ which we wish to prove true
for all natural numbers or positive integers(or in more complicated cases
something that can be reduced to this, but we are not in complicated cases
country here :) )

First we prove that the base case is true, in this problem that is that $P(1)$
is true.

Then we prove that if $P(k)$ is true then $P(k+1)$ is true.

Finaly we can conclude from these that $P(n)$ is true for
all integers $n \geq 1$ by the principle of mathematical induction.

===============================================

In this case $P(n)$ is the proposition:

For all real numbers x, and positive integer n

$1+x+x^2+...+x^n=\frac{x^{n+1}-1}{x-1}$.

The first step is to verify that $P(n)$ is true when $n=1$
(check that this holds in our case now).

The next step is to show that if $P(k)$ is true then $P(k+1)$ is true.

That $P(k)$ is true means that for all real $x$ that:

$1+x+x^2+...+x^k=\frac{x^{k+1}-1}{x-1}$.

If we add $x^{k+1}$ to both sides to get:

$1+x+x^2+...+x^k+x^{k+1}=\frac{x^{k+1}-1}{x-1}+x^{k+1}$.

The LHS of this equation is the required LHS in $P(k+1)$:

$1+x+x^2+...+x^k+x^{k+1}$.

So to show that $P(k+1)$ is true we need to show that the RHS
are equal, that is that:

$\frac{x^{k+1}-1}{x-1}+x^{k+1}=\frac{x^{k+2}-1}{x-1}$.

which I will leave for you to do.

Then as we have shown $P(1)$ is true and that whenever $P(k)$ is true
that $P(k+1)$, we may conclude by mathematical induction that
$P(n)$ is true for all integers $n \geq 1$.

Note: there are more direct methods of proving this result, but here
you are asked to prove it by induction, so that is what we do :)

RonL