# Tagged Questions

For questions about mathematical induction, a method of mathematical proof. Mathematical induction generally proceeds by proving a statement for some integer, called the *base case*, and then proving that if it holds for one integer then it holds for the next integer. This tag is primarily meant ...

86 views

### Prove by induction that $3^{3n+1} + 2^{n+1}$ is divisible by 5

How do I do this? I've tried using logarithms, factoring, but nothing seems to work.
488 views

### Induction proof using Pascal's Identity: $\binom{n}{0}+\binom{n}{i}+…+\binom{n}{n}=2^n$

Prove by induction that for all $n ≥ 0$: $\binom{n}{0}+\binom{n}{i}+....+\binom{n}{n}=2^n$ We should use pascal's identity Base case: $n=0$ LHS: $\binom{0}{0}=1$ RHS: $2^0=1$ Inductive step: ...
34 views

44 views

### Showing that if $xf(x)=\log x$ for $x>0$ then $f^{(n)}(1)=(-1)^{n+1}n!\bigg(1+\dfrac12+\dfrac13+\ldots+\dfrac{1}{n}\bigg)$

Let $f(x)$ be a function satisfying $$xf(x)=\log x$$ for $x>0$. Show that $$f^{(n)}(1)=(-1)^{n+1}n!\bigg(1+\dfrac12+\dfrac13+\ldots+\dfrac{1}{n}\bigg),$$ where $f^{(n)}(x)$ denotes the $n$th ...
66 views

62 views

### Proof by exhaustion:

We are given that a polynomial f(x) has integer coefficients. The coefficient of x^4 being 1. One root of it is ($\sqrt{2}+\sqrt3$). How do we find the other roots? I tried using long division, it ...
140 views

### Proving that $7^n(3n+1)-1$ is divisible by 9

I'm trying to prove the above result for all $n\geq1$ but after substituting in the inductive hypothesis, I end up with a result that is not quite obviously divisible by 9. Usually with these ...
168 views

### Using induction to study the sequence $\sqrt{6} , \sqrt{6 +\sqrt{6}}, \dots$

For the given sequence $\sqrt{6} , \sqrt{6 +\sqrt{6}},\sqrt{6+\sqrt{6+\sqrt{6}}}$ ... Use induction to show the sequence is bounded above by 3 Use induction to show $x_n$ is increasing Find the ...
69 views

### Proving a function by induction [duplicate]

Let $f(n)$ be the function defined by $$f(n) = \frac 1{\sqrt{5}} \left[ \left(1+\sqrt{5}\over2\right)^n- \left(1-\sqrt{5}\over2\right)^n \right]$$ How do you prove that $f(n) = f(n+2) - f(n+1)$ ...
107 views

### Prove $k^2>k+1$ by induction

How would you prove that: $$n^2>n+1 \text{ for } n\ge2$$ using induction? Progress The base is clear, and after that I have assumed $n=k$ and I am trying to prove $(k+1)^2>k+2$ , but I ...
85 views

### Prove by mathematical induction that $\forall n \in \mathbb{N} : \sum_{k=1}^{2n} \frac{(-1)^{k+1}}{k} = \sum_{k=n+1}^{2n} \frac{1}{k}$

Prove by mathematical induction that: $$\forall n \in \mathbb{N} : \sum_{k=1}^{2n} \frac{(-1)^{k+1}}{k} = \sum_{k=n+1}^{2n} \frac{1}{k}$$ Step 1: Show that the statement is true for $n = 1$: LHS = ...
203 views

### Induction Question. Suppose there are n teams in a football league

how can i prove this Let n > 1 be an integer. Suppose there are n teams in a football league and every two teams have played against each other exactly once with no ties. Prove that it is possible to ...
81 views

### Prove that a sequence is increasing [duplicate]

A city's population in the $n^{th}$ year is denoted by $x_n$ (in millions). If, $\forall n \in \mathbb N^+$, we have: $x_1 = \frac34$, $x_{n+1} = 2x_n - x_n^2$, show that as $n \to \infty$, the ...
123 views

### Induction Proof: $\frac{1\cdot 3\cdots (2n-1)}{2\cdot 4\cdots (2n)} \geq \frac{1}{2n}$

Need help proving with induction that $\displaystyle \frac{1\cdot3\cdot5\cdot7...(2n-1)}{2\cdot4\cdot6\cdot8...\cdot2n} \ge \frac 1{2n}$ for all natural numbers $n$. I just can't even get started with ...
87 views

197 views

### Prove that $1^2+2^2+\cdots+n^2=\frac{n(n+1)(2n+1)}{6}$ for $n \in \mathbb{N}$.

Problem: Prove that $1^2+2^2+\cdots+n^2=\frac{n(n+1)(2n+1)}{6}$ for $n \in \mathbb{N}$. My work: So I think I have to do a proof by induction and I just wanted some help editing my proof. My attempt:...
84 views

### Peano's Axioms and Induction

I was reading Landau's Foundations of Analysis. He starts his construction of number systems by stating five axioms. My question is related to the fifth, the axiom of induction: Let there be given a ...
### How does one show that for $k \in \mathbb{Z_+},3\mid2^{2^k} +5$ and $7\mid2^{2^k} + 3, \forall \space k$ odd.
For $k \in \mathbb{Z_+},3\mid2^{2^k} +5$ and $7\mid2^{2^k} + 3, \forall \space k$ odd. Firstly, $k \geq 1$ I can see induction is the best idea: Show for $k=1$: \$2^{2^1} + 5 = 9 , 2^{2^1} + 3 = ...