To prove $\sum_{d|n}\phi(d)=n$. What is the easiest proof for this to tell my first year undergraduate junior. I do not want any Mobius inversion etc only elementry proof. Tthanks!
5847
If $k$ is a positive natural number then $\phi(k)$ denotes the number of natural numbers less than $k$ which are prime to $k$. I have seen proofs that $n = \sum_{k|n} \phi(k)$ which basically partitions $\mathbb{Z}/n\mathbb{Z}$ into subsets of elements of order $k$ (of which there are $\phi(k)$-many) as $k$ ranges over divisors of $n$.  But everything we know about $\mathbb{Z}/n\mathbb{Z}$ comes from elementary number theory (division with remainder, bezout relations, divisibility), so the above relation should be provable without invoking the structure of the group $\mathbb{Z}/n\mathbb{Z}$. Does anyone have a nice, clear, proof which avoids $\mathbb{Z}/n\mathbb{Z}$?
79378
Let $A=(a_{ij})$ be a $n \times n$ matrix with $a_{ij}=\gcd(i,j) , \forall i,j=1,2, \cdots, n$ , then how do we prove $\det A=\prod_{i=1}^n \phi(i)$ ? , where $\phi$ is the Euler's phi function
7838
How can we prove that     $$\sum_{k=0}^{n}\binom{R}{k}\binom{M}{n-k}=\binom{R+M}{n}?$$   (Presumptive) Source: Theoretical Exercise 8, Ch 1, A First Course in Probability, 8th ed by Sheldon Ross.
123407
There is a second part of the problem posted in , from Apostol's book, but I can't figure it out. It asks the reader to prove that if $x \geq 2$ then $\sum\limits_{n\leq x} \frac{n}{\phi(n)} = O(x)$, where the right hand side of the equation uses the Big-O notation. I've tried using the prior result, but I always end up with $O(x^2)$ . Any insights?
50567
Well I attempted to try this but I failed to solve it: So $$\Phi_{p^{n}}(x)= \frac{x^{p^{n}} - 1}{\Phi_{1}(x) \Phi_{p^{2}}(x) \dots \Phi_{p^{n-1}}(x)}$$  Now I'm just stuck here. I saw a result somewhere on the net that said $\Phi_{p^n}(x) = \Phi_p(x^{p^{n-1}})$. I would just use that, but I don't see why that result is true or know how to show that's true.  How do I approach this?
107728
Is there a nice combinatorial proof of the following identity?  (That is, by showing that both sides count the same thing.) $$\sum_{k=0}^n k \cdot k! = (n+1)! -1 $$ I was searching Wikipedia for nice identities to assign to my students for a homework on combinatorial proof, and thought this one looked innocent enough, but then realized I couldn't solve it myself.  Perhaps we should take the set of permutations of $n+1$ letters and partition it in some clever way (maybe the $-1$ suggests that the identity should be set aside), but I can't see what that might be.  Of course it is very easy to prove by induction; that's not what I'm looking for.
102474
I need help with finding the formula and proving it by induction. Am stuck, but the professor says we should know this by now.     Find the formula for $1 + \sum \limits _{j=1} ^n j! j$, and show work proving the formula is correct using induction.
56053
If $\phi(n)$ is the Euler-totient function, how can I show that $\phi(n) \ge \sqrt{n}$?
17821
Given that $\{\phi_n\}$ is a sequence of non-negative numbers whose sum is $1$ and $\{\psi_n\}$ is a sequence of positive numbers, how can I show that  $$ \prod_{n=1}^{\infty}~\psi_n^{\phi_n}~\leq~\sum_{n=1}^{\infty}~\phi_n\psi_n~? $$    Thanks.    PS: I'm not too sure about the title. Perhaps, someone could give it a better title?
46358
Show that $\sum_{i=1}^n (x_i - \bar{x})(y_i - \bar{y}) = \sum_{i=1}^{n} (x_i - \bar{x})(y_i)$. I fell into this hole where I keep finding that $$\sum_{i=1}^n (x_i - \bar{x}) = \sum_{i=1}^n x_i - \sum_{i=1}^n \bar{x} = n\bar{x} - n\bar{x} = 0$$ This seems true, but I know that I am missing something, since this implies that covariance is always zero, which is obviously not true.
71474
Prove $$\sum_{k = 0}^{n}(-1)^{n - k} \binom{n}{k} \cdot k^n = n! \qquad\text{and}\qquad \sum_{k = 0}^{n}(-1)^{n - k} \binom{n}{k} \cdot k^m = 0,$$ where $m \in \{0, 1, 2, \cdots, n - 1\}$.  To be honest, I tried to use some combinatorial ideas but was not able to see interconnections. Also, I had an idea to prove it using induction but failed to do that either. Help will be much appreciated! I just got stuck and don't see any continuation of solution for this problem
68698
Do you have any idea to prove the following identity via a combinatorial (or algebraic) method?  $\sum_{n=r}^{n=\infty} {n \choose r}^{-1} = \frac{r}{r-1}$  This is  of the book Chen C.C., Koh K.M. Principles and techniques in combinatorics. The book does not give a solution, although it mentions: "see H. W. Gould, Combinatorial Identities, Morgantown, W.V. (1972), 18-19".  many thanks in advance, Shahram
70092
I am trying to show that: \begin{equation} \frac{n}{\phi(n)} = \sum_{d \mid n} \frac{\mu^2(d)}{\phi(d)} \end{equation} where $\phi(n)$ is  and $\mu$ is the .  The identity clearly holds for $n=1$, so if we write $n=p_1^{a_1} \cdots p_k^{a_k}$ for the prime decomposition of $n$, the left-hand side becomes: \begin{eqnarray*} \frac{n}{\phi(n)} &amp; = &amp; \frac{p_1^{a_1} \cdots p_k^{a_k}}{\phi(p_1^{a_1}) \cdots \phi(p_k^{a_k})} \\ &amp; = &amp; \frac{p_1^{a_1} \cdots p_k^{a_k}}{(p_1^{a_1-1})(p_1-1) \cdots (p_k^{a_k})(p_k-1)} \\ &amp; = &amp; \frac{p_1 \cdots p_k}{(p_1-1)\cdots (p_k-1)} \end{eqnarray*}   Whereas the right-hand side becomes:  \begin{eqnarray*} \sum_{d \mid n} \frac{\mu^2(d)}{\phi(d)} &amp; = &amp; \sum_{\substack{d \mid n \\ p^2 \nmid d}} \frac{1}{\phi(d)} \\ &amp; = &amp; 1 + \frac{1}{\phi(p_1)} + \dots + \frac{1}{\phi(p_k)} + \frac{1}{\phi(p_1 p_2)} + \dots + \frac{1}{\phi(p_{k-1}p_k)} \\ &amp; + &amp; \dots + \frac{1}{\phi(p_1 \cdots p_k)} \\ &amp; = &amp; 1 + \frac{1}{p_1 - 1} + \dots + \frac{1}{p_k - 1} + \frac{1}{(p_1 - 1)(p_2 - 1)} + \dots + \frac{1}{(p_{k-1}-1)(p_k-1)} \\ &amp; + &amp; \dots + \frac{1}{(p_1 - 1) \cdots (p_k - 1)} \end{eqnarray*}  I am unsure of how to proceed from this point however. Any help would be much appreciated.
120789
Prove that if $n \in \mathbb{N}$, then $$\sum_{d|n}{(d(n))^3}=(\sum_{d|n}{d(n)})^2$$ where $d(n)$ is the divisor function. I have know only information is $d(n)=\sum_{d|n}{1}$.
118721
I'm undergraduate student of mathematics.  I need to prove: $$\sum_{k=0}^{n} \binom{2n}{2k}= 2^{2n-1}$$ Can you please help me
104441
I'm interested in the different ways of proving this, any proof is welcome. I understand one way is the cosine sum/difference formula, another is using a right angled triangle. Are there any others? Thanks.
27132
I want to prove that if $d \mid n \in \mathbb{N}$, then $\varphi(d) \mid \varphi(n)$.  It's given that $d \mid n$, so we know that $n = dm$, for some $m \in \mathbb{Z}$. Now, I want to show that $\varphi(d) \mid \varphi(n)$, i.e. that $\varphi(n) = k\varphi(d)$, for some $k \in \mathbb{Z}$. Drawing a blank of where to go from here.