# Tag Info

## Hot answers tagged induction

7

Here is another one. Prove that the power of $13$ can be writen as a sum of two squares. I will give two proofs of it. First one is more involved and includes lemma $$(a^2+b^2)(x^2+y^2)= (ax+by)^2+(bx-ay)^2$$ yet second takes step 2 and it is much more elegant. 1.st proof Base: $n=1$, then $13 = 2^2+3^2$ and we are done. We know that $13^n = a^2+b^2$ ...

4

A simple consequnce of: Postage Stamp Problem, which states that for any two relatively prime positive integers $m,n$, the greatest integer that cannot be written in the form $am + bn$ for nonnegative integers $a, b$ is $mn-m-n$, is that every natural number greater or equal to $mn-m-n+1$ can be writen in a form $am+bn$ for some $a,b$. And for some ...

3

Putnam 1963 Let $\mathbb N$ be the set of positive integers, and let $f:\mathbb N\to\mathbb N$ be a strictly increasing function such that $f(2)=2$ and $f(m)f(n)=f(mn)$ for all positive integers $m,n$ such that $\gcd(m,n)=1$. Find all such functions $f$. Watered down version: Let $\mathbb N$ be the set of positive integers, and let $f:\mathbb N\to\... 3 For what natural$n$does there exist a square composed of$n\$ squares? Example: 1, 4, and 6 are valid, but one cannot construct a square from 2, 3, or 5 squares. Proof:

2

Hmm, I'm surprised than no one mentioned de Moivre's formula: $$(\cos \phi +i\cdot \sin \phi)^n= \cos (n\phi) + i\cdot\sin (n\phi)$$ It is an excellent theorem to prove where we must also use the addition theorem for sin and cos.

1

Prove that, for all x in N, we have x+1 =/= x. (Requires use of proof by contradiction.) Use only the following properties of addition on N: Addition is closed on N. x+1 =/= 1 for all x in N. If x+1 = y+1, then x=y for all x, y in N. The Principle of Mathematical Induction. OUTLINE Base case 1+1 =/= 1 follows directly from (2). Inductive step ...

Only top voted, non community-wiki answers of a minimum length are eligible