Tagged Questions

4
votes
3answers
80 views

proving $n!>2^n\;\;\forall \;n≥4\;$ by mathematical induction

My teacher proved the following $n!>2^n\;\;\;\forall \;n≥4\;$ in the following way Basis step: $\;\;4!=24>16$ ok Induction hypothesis: $\;\;k!>2^k$ Induction step: ...
2
votes
1answer
47 views

Prove that $n^2 \leq \frac{c^n+c^{-n}-2}{c+c^{-1}-2}$.

Let $c \not= 1$ be a real positive number, and let $n$ be a positive integer. Prove that $$n^2 \leq \frac{c^n+c^{-n}-2}{c+c^{-1}-2}.$$ My initial thought was to try and induct on $n$, but the ...
1
vote
1answer
64 views

Prove that for any $n \in \mathbb{N}, 2^{n+2} 3^{n}+5n-4$ is divisible by $25$?

I have question Q Prove that for any $n \in \mathbb{N}, 2^{n+2} 3^{n}+5n-4$ is divisible by $25$? by using induction Thanks
2
votes
2answers
86 views

Proving $r_0+r_1a+r_2a^2+\cdots+r_{k-1}a^{k-1} < a^k$ by INDUCTION.

Let $a$ be a natural number $>1$. For all integers $r_0, r_1, \dots, r_{n-1}$ with $0\leq r_{j} < a$, then \begin{eqnarray} r_0+r_1a+r_2a^2+\cdots+r_{n-1}a^{n-1} < a^n. \end{eqnarray} ...
3
votes
4answers
101 views

Is this a valid proof by induction?

I want to prove by induction that $a^n \mid b^n$ implies that $a \mid b$ holds for all integers $n\geq 1$. clearly for $n=1$ this is true, since if $a \mid b$, then $a \mid b$. Suppose this is true ...
2
votes
1answer
54 views

associativity of multipication of natural numbers

I am trying to prove by induction the associativity of natural numbers. It is easy to see that if $n,m\in \mathbb{N}$, then $(mn)1=m(n1)$. If $p\in \mathbb{N}$ is such that $(mn)p= m(np)$, then ...
15
votes
5answers
467 views

IMO 1987 - function

Show that there is no function $f: \mathbb{N} \to \mathbb{N}$ such that $f(f(n))=n+1987, \ \forall n \in \mathbb{N}$.
3
votes
3answers
56 views

The number of positive integers which are less than $mk$ and coprime to $m$ is $k\phi(m)$.

Let $m,k$ be positive integers. Then the number of positive integers $\leq mk$ prime to $m$ is $k\phi(m)$. My approach would be to use induction on $k$. If $k=1$, then by definition the result ...
2
votes
3answers
116 views

Something kind of like proving the euclidean Algorithm by induction

Let a > b be positive integers. In applying the Euclidean algorithm, we have $a = b q_0$ + $r_0$, $b = r_0 q_1 + r_1$, and $r_{n-1} = r_n q_{n+1} + r_{n+1}$, for all $n > 0$. Prove by induction ...
0
votes
2answers
254 views

Factorial (Proof by Induction)

Prove by induction that $n!<n^n$ for all $n>1$. So far I have (using weak induction): Base Case: Proved that claim holds for $n=2$ Induction hypothesis: For some arbitrary $n>1, n!<n^n$ ...
2
votes
2answers
90 views

$9^n \equiv 1 \mod 8$

I would like someone to check this inductive proof (sketch) The base case is clear. For the inductive step, it follows that $8 \mid 9^{n+1} - 9 = 9(9^n - 1)$ by the indutive hyp. So $9^{n+1} \equiv ...
12
votes
5answers
301 views

Alternate proof that for every natural number $n,\ \left\lfloor\left(\frac{7+\sqrt{37}}{2}\right)^n\right\rfloor$ is divisible by $3$

Original Problem: Prove that for every natural number $n$,$$\left\lfloor\left(\frac{7+\sqrt{37}}{2}\right)^n\right\rfloor$$ is divisible by $3$. I found the problem in the book Winning ...
1
vote
4answers
127 views

Proving that $\alpha^{n-2}\leq F_n\leq \alpha^{n-1}$ for all $n\geq 1$, where $\alpha$ is the golden ratio

I got stuck on this exercise. It is Theorem 1.15 on page 14 of Robbins' Beginning Number Theory, 2nd edition. Theorem 1.15. $\alpha^{n-2}\leq F_n\leq \alpha^{n-1}$ for all $n\geq 1$. Proof: ...
2
votes
1answer
72 views

Simple Fibonacci / Lucas Numbers Relationship

Prove the identity by induction: $$ F_{2n} = F_n L_n, $$ where $F_n$ and $L_n$ are the $n^{th}$ Fibonacci and Lucas number, respectively. I have an answer but am not happy with it since it doesn't ...
1
vote
4answers
132 views

Using induction to prove $3$ divides $\left \lfloor\left(\frac {7+\sqrt {37}}{2}\right)^n \right\rfloor$

How can I use induction to prove that $$\left \lfloor\left(\cfrac {7+\sqrt {37}}{2}\right)^n \right\rfloor$$ is divisible by $3$ for every natural number $n$?
2
votes
0answers
232 views

Induction in proof of multiplicativity of Euler totient function

(Updated below) I'm working through John Stillwell's Elements of Algebra, and while his exercises are generally crafted to be not too difficult, there's one that I don't even understand what it's ...
5
votes
2answers
234 views

Odd Binomial Coefficients?

By Newton's Formula: $$(a+b)^n = \sum_{k=0}^n \binom{n}{k} a^{n-k}b^k $$ Proof that every $\dbinom{n}{k}$ is odd if and only if $n=2^r-1$. I have already shown that if $n$ is of the form $2^r-1$, ...
7
votes
2answers
178 views

Inductive proof that $(m!^n)n! \mid (mn)!$

I have worked this problem out before but am stuck on the inductive step. Show that $(m!^n)n! \mid (mn)!$ I am using induction on $n$. I thought to factor $(m(n+1))$! but can't get it ...
1
vote
2answers
57 views

How to prove $k^n \equiv 1 \pmod {k-1}$ (by induction)?

How to prove $k^n \equiv 1 \pmod {k-1}$ (by induction)?
2
votes
3answers
155 views

When is induction needed?

What is a theorem about the positive integers that cannot (or is not known to) be proved without induction over the positive integers?
3
votes
2answers
205 views

$f_n$ is divisible by $4$ if and only if $n$ is divisible by $6$

I thought I had this question down, but while looking over my solution, I think I'm missing a step. I want to show for $f_n$ the nth fibonacci number, that $f_n$ is divisible by $4$ if and only if ...
8
votes
11answers
4k views

Proof that $n^3+2n$ is divisible by 3

I'm trying to freshen up for school in another month, and I'm struggling with the simplest of proofs! Problem: For any natural number n , n3 + 2n is divisible by 3. This makes sense ...