I have just learned something about universal Generalization in discrete math, and want to know how to prove it. It is
24373
This is an excerpt from Discrete Mathematics.     Universal generalization is the rule of inference that states that ∀xP(x) is true, given the premise that P(c) is true for all elements c in the domain. Universal generalization is used when we show that ∀xP(x) is true by taking an arbitrary element c from the domain and showing that P(c) is true. The element c that we select must be an arbitrary, and not a specific, element of the domain.       That is, when we assert from ∀xP(x) the existence of an element c in   the domain, we have no control over c and cannot make any other   assumptions about c other than it comes from the domain. Universal   generalization is used implicitly in many proofs in mathematics and is   seldom mentioned explicitly. However, the error of adding unwarranted   assumptions about the arbitrary element c when universal   generalization is used is all too common in incorrect reasoning.   I have two questions:  1. What is meant by the second paragraph ?  2. How come just by taking arbitrary c in domain, we can conclude that if P(c) is true then so is ∀xP(x). (There may exist some counterexamples).
54080
I do not know an example. Will ask question if in doubt of the proofs provided thank you!!
120815
So, here is the question:  For any position integer $n$, let $T(n)$ be the number 1 if $n&lt;4$ and the number $T(n-1) + T(n-2) + T(n-3)$ if $n \geq 4$.  We have $T(1)=1, T(2)=2, T(3)=3$ $$T(4)=T(3)+T(2)+T(1) = 1+1+1+1 = 3$$  $$T(5) = T(4)+T(3)+T(2) = 3+1+1 = 5$$  Prove that: (Universal n is an element of all positive integers), $T(n)&lt;2^n$  Any suggestions?
84323
The question reads     $$U_n = (1+x)^n - 1 - nx$$   Show that $U_2 \geq 0$   Hence or otherwise show that $(1+x)^n \geq 1 + nx$ for all $x \gt -1$.   Obviously the $U_2 \geq 0$ is very easy, I can do that without any trouble but I cannot see how it links to the 2nd part of the question.
64886
That's a problem I proved (quite a while back) in tiny Rudin. However, I don't really get it. The other questions were actually useful results - I don't think I've ever come near using this result. Surely it's going to be close to apparent that you're working in an uncountable set?  For instance, examples where this result could be applied but it is hard otherwise to tell that the space is uncountable?
75449
Just would like to see if I'm right.  Proof: Let $G$ be generated by $x$ (Let $G=\langle x \rangle$ for some $x$ in $G$.) We wish to show that there exists an $x'$ in $G'$ such that $G'=\langle x' \rangle$. First, we will show that for all $x^n$ in $G$, $f(x^n)=f^n(x)$. We proceed by induction.   Base case: $n=1$. $f(x*e_G)=f(x)f(e_G)=f(x)$. Now, assume that $f(x^k)=f^k(x)$ for some arbitrary positive integer k. We show that $f(x^{k+1})=f^{k+1}(x)$. Observe that $f(x^{k+1})=f(x^kx)=f(x^k)f(x)=f^k(x)f(x)=f^{k+1}(x).$   Next we will show that for all $x^{-n}$ in $G$, $f(x^{-n})=f^{-n}(x)$. We proceed by induction. Base case: $n=-1$. $f(x^{-1}*e_G)=f(x^{-1})f(e_G)=f(x)$. Now, assume that $f(x^{-k})=f^{-k}(x)$ for some arbitrary positive integer k. We show that $f(x^{-k-1})=f^{-k-1}(x)$. Observe that $f(x^{-k-1})=f(x^{-k}x)=f(x^{-k})f(x)=f^{-k}(x)f(x)=f^{-k-1}(x).$ Because $f$ is onto, $Im(f)=G'$ and therefore $Im(f)=(...,f^{-2}(x),f^{-1}(x),e_G,f(x),f^2(x),...)=G'$.  Thus, there exists an $x'$ in $G'$ such that $G'=\langle x' \rangle$ and the proof is complete by the principle of mathematical induction. Q.E.D.  I have a feeling the proof shouldn't be this long. Any suggestions for a shorter, cleaner proof?
63370
I couldn’t find any proof on the internet. I would appreciate an elementary proof , but any help would be appreciated!  Thank you.
25736
I need some advice as I am struggling with the following combinatorics exercise.  Let $k$ be a given positive integer. Show that any non-negative integer $N$ can be written uniquely in the form $$N=\binom{x_k}{k}+\binom{x_{k-1}}{k-1}+\dots+\binom{x_1}{1},$$ where $0 \leq x_1 &lt; \dots &lt; x_{k-1} &lt; x_k$.  The exercise is accompanied by this advice:  Let $x$ be such that $\binom{x}{k} \leq N &lt; \binom{x+1}{k}$. Then any possible representation has $x_k = x$. Now use induction and the fact that $N-\binom{x}{k} &lt; \binom{x}{k-1}$ to show the existence and uniqueness of the representation.  I am really stuck and thus grateful for the slightest hint on how to solve it.
121034
I am trying to improve my discrete Math skills by doing some proof exercises. But I am struggling to understand how to start proving the following hypothesis:  $$ S = {x}_1{y}_1 + {x}_2{y}_2 + \ldots + {x}_n{y}_n $$ Where ${x}_1,{x}_2\ldots{x}_n$ and ${y}_1,{y}_2\ldots{y}_n $ are ordering of two different sequences of positive real numbers, each containing n elements. S takes its maximum value when ${x}_1,{x}_2\ldots{x}_n$ and ${y}_1,{y}_2\ldots{y}_n $ are sorted in non decreasing order.  I was thinking that I should maybe use a proof by contradiction. Where the negation of the hypothesis is: S takes it minimum value over all ordering of the two sequences when both sequences are sorted into non increasing order.  However I am not sure my negation of the hypothesis is correct or how proceed from there. I do not want the complete proof because I am trying to learn how to do it myself but if some one can tell me how to make a start on this I would be grateful.
39985
Prove by induction:   $$\sum_{i=1}^{n} i \cdot 2^i = (n-1) \cdot 2^{n+1} +2$$   Basis: let $p(n)$ be the predicate.  Let $n=1$ this gives $(1-1) \cdot 2^1+1+2 = 2$ and $1 \cdot 2^1 = 2$ so its true for $p(1)$  Induction: assume $n=k$ thus $$\sum_{i=1}^{k} i \cdot 2^i = (k-1) \cdot 2^{k+1} +2$$  when $n=k+1$:  $$\sum_{i=1}^{k+1} i \cdot 2^i = \sum_{i=1}^{k} i \cdot 2^i + ((k+1)-1) \cdot 2^{(k+1)+1} +2$$  $$ =(k-1) \cdot 2^{k+1} +2 + ((k+1)-1) \cdot 2^{k+2} +2$$  $$= 2^{k+1}k - 2^{k+1} +2 +2^{k+2}(k+1) - 2^{k+2}+2$$  $$=\frac{2^{k+1}k-2^{k+1}+2 \cdot 2^{k+1}(k+1)-2 \cdot 2^{k+1} +4}{2}$$  $$=2^{k+1}k-2^{k+1}+2^{k+1}(k+1)-2^{k+1}+2$$  $$= (k-1) \cdot 2^{k+1}+((k+1)-1) \cdot 2^{k+1} +2$$  I've been messing around with the arithmetic part of this for a while now and it's getting frustrating, I'm thinking that I've possibly made a mistake at the beginning of the induction step and that's why I cant get this to work, or maybe I'm just missing something in the algebra, either way can someone please help.
44541
I have looked extensively for a proof on the internet but all of them were too obscure. I would appreciate if someone could lay out a simple proof for this important result. Thank you.
87658
Prove there exists an isomorphism from the semigroup of natural numbers under multiplication to the semigroup of odd natural numbers under multiplication.  An example would be helpful.
74827
This statement is used without proof in various sources (incl. Ziegler's &quot;Lectures on polytopes&quot; and Gruber's &quot;Convex and discrete geometry&quot;), yet I don't have any idea how to prove it, or have intuition about it in $n&gt;3$ dimensions. Someone suggested me to use a concept of dual polytope to prove it, I have not explored it thoroughly and maybe someone can help with understanding how duality is convenient here.
115780
How can we prove that for every pair $N \in \mathbb{N}$, and natural number $\beta\in [2, \infty)$ there exists a unique set of integers $x_i \in [0, \beta -1]$, $k\in [0,\infty)$ such that:  $$N = \sum_{i=0}^{k}\beta^ix_{i}, \quad $$  It's a question if every positive integer has its unique representation in every base $\beta$. Is the validity of above statement somehow related to Horner's rule?
68476
Here's how it is.  So I was studying some notes on Discrete Structures then I discovered this. Prove that $2^N = \binom{N}{0} + \binom{N}{1} + \binom{N}{2} + \dots + \binom{N}{N}$ Since I was new to this, I didn't quite understand it.  I tried using the binomial expansion but it confused me a little.  Can someone please help me solve this.  That would be great.
95239
Here is the proof:     But I do not understand the following:  1-why the function needed to be bilinear to use the universal property?  2- what is he doing starting from the paragraph that starts with the statement "In the other direction ...." ?
35166
There are several proofs I have seen of this, but they all seem to use choice subtely at some point. Is there any way to prove this without choice, or is it possibly unproveable?