All Questions
15
questions
2
votes
1
answer
127
views
Show that the product of the $2^{2019}$ numbers of the form $\pm 1\pm \sqrt{2}\pm\cdots \pm \sqrt{2019}$ is the square of an integer.
Show that the product of the $2^{2019}$ numbers of the form $\pm 1\pm \sqrt{2}\pm\cdots \pm \sqrt{2019}$ is the square of an integer.
I'm aware very similar problems were asked before (e.g. here and ...
4
votes
3
answers
666
views
Representing the cube of any natural number as a sum of odd numbers
I'm expanding my notes on exercises from Donald Knuth's The Art of Computer Programming, and found something rarely mentioned in the Internet, but still useful to prove Nicomachus' Theorem about the ...
3
votes
6
answers
185
views
Proof that: $(a-b)\cdot\Bigg(\sum_{k=0}^{n}a^{n-k}b^{k}\Bigg)=a^{n+1}-b^{n+1}\text{ }\forall n\in\mathbb{N_{0}}$
I'm trying to prove a more general version of the 3rd binomial equation via mathematical induction which will help me complete another proof.
$$(a-b)\cdot\Bigg(\sum_{k=0}^{n}a^{n-k}b^{k}\Bigg)=a^{n+1}...
3
votes
1
answer
99
views
How to prove $\theta(2^r) \leq 2^{r+1}\log2$
Show that $\theta(2^r) \leq 2^{r+1}\log2$ where $\theta(n)= \sum_{p\leq n}\log p$ where $p$ is prime.
I have approached by induction: let $\theta(2)=\log2$ and $\theta(2^r) \leq 2^{r+1}\log2$ then
$$\...
0
votes
2
answers
60
views
prove by induction expression
Show that for all natural numbers $n$, the following equality holds:
$$\sum_{i=1}^{n}\frac{1}{2i(2i-1)} = \sum_{i=n+1}^{2n}\frac{1}{i}$$
Can't seem to wrap my head around it...
1
vote
1
answer
80
views
Is this a valid mathematical induction proof?
The required is to prove that $\sum_{i=1}^n 1 = n$
So here's my attempt
Prove that it works for n = 1
$$\sum_{i=1}^1 1 = 1$$ $$ 1 = 1$$
Assume it works for k
$$\sum_{i=1}^k 1 = k$$
Show that it ...
3
votes
4
answers
442
views
Proving for all integer $n \ge 2$, $\sqrt n < \frac{1}{\sqrt 1} + \frac{1}{\sqrt 2}+\frac{1}{\sqrt 3}+\cdots+\frac{1}{\sqrt n}$ [duplicate]
Prove the following statement by mathematical induction:
For all integer $n \ge 2$, $$\sqrt n < \frac{1}{\sqrt 1} + \frac{1}{\sqrt 2}+\frac{1}{\sqrt 3}+\cdots+\frac{1}{\sqrt n}$$
My attempt: Let ...
5
votes
0
answers
525
views
Sum of like powers equal to a power
It's not hard to prove that $$(1+2+3+\ldots+n)^2=1^3+2^3+\ldots+n^3$$ ( for example using induction )
A generalization of this is also known :
$$(\sum_{d \mid n} \tau(d))^2=\sum_{d \mid n} \tau(d)^3$...
3
votes
3
answers
10k
views
Double induction example: $ 1 + q + q^2 + q^3 + \cdots + q^{n-1} + q^n = \frac {q^{n+1}-1}{q-1} $
I'm working on a double induction problem with the following prompt:
Prove by induction on $n$ that for any real number $q > 1$ and integer $n \ge 0$:
$$ 1 + q + q^2 + q^3 + \cdots + q^{n-1} + ...
0
votes
1
answer
19
views
How many ways are there to express a natural as a sum of 3 others—but by induction?
I have figured out an (inductive?) process, but I cannot express it formally:
There is always one possibility where $n$ is in the first place of our 3-tuple: $[n~~0~~0]$. Then I can subtract $k~(\leq ...
1
vote
1
answer
359
views
Prove summations are equal
Prove that:
$$\sum_{r=1}^{p^n} \frac{p^n}{gcd(p^n,r)} = \sum_{k=0}^{2n} (-1)^k p^{2n-k} = p^{2n} - p^ {2n-1} + p^{2n-2} - ... + p^{2n-2n}$$
I'm not exactly sure how to do this unless I can say:
...
1
vote
2
answers
351
views
Inductive proof of the identity $\binom{n} {0} F_0+\binom{n}{1} F_1+\binom{n}{2} F_2+\cdots +\binom{n}{n} F_n=F_{2n}$ [duplicate]
I'm trying to prove the following identity:
$$\binom{n} {0} F_0+\binom{n}{1} F_1+\binom{n}{2} F_2+\cdots +\binom{n}{n} F_n=F_{2n}$$
I need to prove it using induction (not a counting argument), I ...
4
votes
1
answer
94
views
$\sum_{k=0}^{n}(-1)^k {{m+1}\choose{k}}{{m+n-k}\choose{m}}$
I'm supopsed to show that if $m$ and $n$ are non-negative integers then
$$\sum_{k=0}^{n}(-1)^k {{m+1}\choose{k}}{{m+n-k}\choose{m}}
= \left\{
\begin{array}{l l}
1 & \quad \text{if $n=0$}\\
...
2
votes
1
answer
177
views
Critique on a proof by induction that $\sum\limits_{i=1}^n i^2= n(n+1)(2n+1)/6$?
I need to make the proof for this
1:$$1^2 + 2^2 + 3^2 + ... + n^2=\frac{(n(n+1)(2n+1))}{6}$$
By mathematical induction I know that,
If P(n) is true for $n>3^2$ then P(k) is also true for k=N and ...
16
votes
4
answers
17k
views
Induction Proof that $x^n-y^n=(x-y)(x^{n-1}+x^{n-2}y+\ldots+xy^{n-2}+y^{n-1})$
This question is from [Number Theory George E. Andrews 1-1 #3].
Prove that $$x^n-y^n=(x-y)(x^{n-1}+x^{n-2}y+\ldots+xy^{n-2}+y^{n-1}).$$
This problem is driving me crazy.
$$x^n-y^n = (x-y)(x^{n-1}+...