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 ...

learn more… | top users | synonyms

1
vote
1answer
97 views

7) Prove that $2n-3 \leq 2^{n-2}$ for all $n \geq 5$ by mathematical induction [duplicate]

Prove that $2n-3\leq 2^{n-2}$ , for all $n \geq 5$ by mathematical induction I have to prove by mathematical induction that: $2n-3\leq 2^{n-2}$ , for all $n \geq 5$
0
votes
2answers
60 views

Prove that $2n-3\leq 2^{n-2}$ , for all $n \geq 5$ by mathematical induction

Prove that $2n-3\leq 2^{n-2}$ , for all $n \geq 5$ by mathematical induction I have to prove by mathematical induction that: $2n-3\leq 2^{n-2}$ , for all $n \geq 5$ Thank you for the Review.
3
votes
4answers
161 views

Is this backwards reasoning?

Yesterday I was answering a question on induction: Certain step in the induction proof $\sum\limits_{i=0}^{n} i^2 = \frac{n(n+1)(2n+1)}{6}$ unclear Basically, I was proving a certain formula using ...
0
votes
1answer
357 views

Proof by induction that if $\text{five}(0) = 10$ and $\text{five}(n+1) = \text{five}(n) + 5$ then $\text{five}(j) = 5(j+2)$ for all $j$

Let the function ${\rm five}(n)$ be a function defined by the two equations: ${\rm five}(0) = 10 \\ {\rm five}(n+1) = {\rm five}(n) + 5$ Prove that: ${\rm five}(j) = 5*(j + 2)$ ...
2
votes
3answers
76 views

Factoring/approximating an apparently simple formula

Does anyone know if the following formula can be factorized or approximated: $a^3 + b^3 + c^3 + a^2b + ab^2 + a^2c + ac^2 + b^2c + bc^2 + abc$ It looks a lot like $(a + b + c)^3$, except for the ...
2
votes
6answers
281 views

Certain step in the induction proof $\sum\limits_{i=0}^{n} i^2 = \frac{n(n+1)(2n+1)}{6}$ unclear

It's about proving the following: $$\sum\limits_{i=0}^{n} i^2 = \frac{n(n+1)(2n+1)}{6}$$ I understand every step in the master solution, however, I have no idea how one can know by intuition to ...
2
votes
1answer
44 views

Proving that there exists $w$ such that $4x < 6w < 6x$ and $\gcd(w,\frac{x\#}{6})=1$ where $x \ge 7$ and $x\#$ is the primorial

I am trying to show that for any integer $x \ge 7$, there exists $w$ with the following properties: $4x < 6w < 6x$ $\gcd\left(6w,\frac{x\#}{6}\right)=1$ I thought that this would be pretty ...
9
votes
8answers
954 views

Induction without a base case [duplicate]

I am looking for an example where you have $P(n)$ implying $P(n+1)$. However there is no base case. For which there is therefore no solution at all for the induction problem even though the inductive ...
0
votes
1answer
50 views

How to prove $x_{n+1}y_n-x_ny_{n+1}=2^{3n}\sqrt{7}$

For $n \in \mathbb{N}$ let $z_n=(1-i\sqrt {7})^n, ~x_n = Re~z_n,~y_n = Im~z_n$. I want to show the following: $x_{n+1}y_n-x_ny_{n+1}=2^{3n}\sqrt{7} ~~~(n \in \mathbb{N})$ My only idea was to show ...
0
votes
1answer
61 views

function proving with induction [closed]

I'm having trouble with the following past paper question : Consider the function $take: \Bbb N \to \Bbb N$ defined recursively as follows: Base case: $take(0) = 100$ Recursive case: ...
1
vote
2answers
57 views

manipulation of subtraction

I am trying to solve an induction problem and got stuck at this part. $$ 1 - \frac{n+2}{(n+2)!} + \frac{n+1}{(n+2)!} = 1 - \frac{(n+2) - (n+1)}{(n+2)!} $$ Shouldn't it be $$ 1 - \frac{n+2}{(n+2)!} ...
-1
votes
2answers
85 views

Showing $(n+1)^n<e^nn!$ by induction

Show $(n+1)^n<e^nn!$ I know why that would be the case using general knowledge and a bit of substitution but am clueless on how to prove it.
0
votes
1answer
55 views

proof by induction, how to start with the specific example. 5^n - 1 is divisible by 4

I am looking at proof by induction as part of my maths module for my upcoming examination. I ave worked through several problems of induction, but i am not yet fully capable. The problem i have been ...
1
vote
4answers
3k views

Prove that $ n^3 + 5n$ is divisible by 6 for all $n\in \textbf{N}$ [duplicate]

Prove that $ n^3 + 5n $ is divisible by 6 for all $ n \in \textbf{N} $. I provide my proof below.
4
votes
2answers
572 views

Prove that $ 1^2 + 3^2 + … + (2n-1)^2 = \displaystyle \frac{4n^3 -n}{3} $

Prove that $ 1^2 + 3^2 + ... + (2n-1)^2 = \displaystyle \frac{4n^3 -n}{3} $. I provide the answer below.
1
vote
1answer
38 views

Question about mathematical induction

Given $a_1=\frac{1}{2}(a_0+\frac{A}{a_0})$, $a_2=\frac{1}{2}(a_1+\frac{A}{a_1})$, $a_{n+1}=\frac{1}{2}(a_n+\frac{A}{a_n})$ for $n\ge2$ where $a>0$ and $A>0$; prove that $$ {a_n-\sqrt{A} \over ...
1
vote
1answer
92 views

How do I prove $F_{n+1}^2 - F_nF_{n+2} = (-1)^n$ using induction? [duplicate]

$F_n$ refers to the $n$ term of the Fibonacci Sequence. I think I'm supposed to prove this by induction. I already have the base case. I am at: $\text{F}_\text{k+1}^2 - F_k\text{F}_\text{k+2} + ...
1
vote
0answers
64 views

Generalization of simple and transfinite induction

Definition For a set of ordinals $\boldsymbol\alpha$ and ordinals $\gamma$, $\beta$, let $$\boldsymbol\alpha \xrightarrow[\gamma]{}\beta$$ symbolize the proposition that ...
0
votes
2answers
38 views

Show that $D^m=S^{-1}\cdot M^m \cdot S$

I have to show, that $D^m=S^{-1}\cdot M^m \cdot S$ for all $m \geq 1$, given that M is diagonalizable with diagonal matrix $D=S^{-1}\cdot M \cdot S$. (As side question: is it true if I say that D is a ...
2
votes
1answer
107 views

How to prove $(n!)^4\le2^{n^2+n}$?

This may sound like a newbie but question is to show that $$(n!)^4\le2^{n^2+n} for \quad n=1,2,3...$$ I know it is true for n=1. $(1!)^4\le2^2$ and assume it is true for $1<m\le n$ for ...
0
votes
3answers
115 views

Estimate the factorial $n!$ starting with the integral of $1/x$

This is a 3-part problem concerning an estimate for the factorial $n!$ a. By considering the graph of $y=\frac{1}{x}$ explain why $$\frac{1}{k+1} < \int\limits_{k}^{k+1} \frac{\mathrm ...
1
vote
2answers
184 views

Proof determinant of transpose Vandermonde matrix is $\prod_{1\le i\lt j\le n}(\alpha_i-\alpha_j)$

the below is a transpose Vandermonde matrix determinant equality. I have seen a lot of proofs of its determinant being $=\prod_{1\le i\lt j\le n}(\alpha_j-\alpha_i)$, but this ones indices are ...
0
votes
1answer
65 views

Is my mathematical induction answer correct or not?

I prove that using following steps. Please tell me my answer is correct or not?
1
vote
1answer
48 views

Proving $\prod \limits_{k=0}^{n}(1-a_k) \geq1- \sum\limits_{k=0}^{n}a_k$

Let $(a_n)_{n \in \mathbb{N}}$ a sequence of real numbers with $0 \leq a_n \leq 1$ for all $n \in \mathbb{N}$. I want to prove the following inequality using mathematical induction: $\prod ...
1
vote
4answers
180 views

Prove using induction : $n < 3^n$

$ p(n) = n < 3^n = q(n) $ when $n=1$, $p(n)=1< 3=q(n)$ Assume the result is true for $n=m$ $p(m)=m < 3^m$ when $n = m+1$ $p(m+1) = m+1 < 3^m +1<3*3^m = 3^{m+1}=q(m+1)$ is this ...
1
vote
2answers
107 views

Prove that $(x_{n})$ is bounded above by $4$

Let, $(x_{n})$ be a sequence define recursively by, $x_{1}=1$ and $x_{n+1}=\frac{1}{2}(x_{n}+\sqrt{3x_{n}})$. Verify that the sequence is bounded above by 4. By induction we have: for $n=1$, ...
3
votes
2answers
100 views

What is the meaning of $n\in \aleph$

Using mathematical induction, prove that, for each $n\in \aleph$ $$n<3^n$$ Dear all, what is the meaning of "$n\in \aleph$" . How to substitute it and prove that? please give me one step ...
1
vote
2answers
46 views

algebra help in AoCP intro to induction

In the introduction of mathematical induction, section 1.2.1 of Knuth's Art of Computer Programming, I'm struggling with (4) especially this relation: $\phi^{n-2} +\phi^{n-1} = \phi^{n-2}(1+\phi)$ ...
0
votes
1answer
128 views

Binomial coefficients identity (sum of the powers of the natural numbers)

I've found exercise with binomial coefficients in Kostrikin's book. Proof that $\sum_{i=1}^n{{r+1}\choose{i}}\left(1^i+2^i+\dots+n^i\right)=(n+1)^{r+1}-(n+1)$ I was trying to check that for ...
1
vote
3answers
46 views

Divisibility Mathematical Induction Help

Could you please help me with this question prove that $\displaystyle5^n + 2\cdot(11)^n$ is a multiple of $3$. Thanks
4
votes
2answers
128 views

Induction without base case?

I'm doing a bit of research on set theory. So far it's quite interesting. Right now I'm reading about transfinite induction. The book states the following theorem about induction in a well-ordered ...
-2
votes
3answers
246 views

Horner Polynomial Evaluation: counting addition operations

We first note how the polynomial in Exercise 5 can be written in the nested multiplication method: ...
3
votes
4answers
405 views

Induction proof for $n\in\mathbb N$, $9 \mathrel| (4^n+6n-1)$

Prove that for all $n\in\mathbb N$, $9 \mathrel| (4^n+6n-1)$. I have shown the base case if $n=0$ (which is a natural number for my course). I'm now trying to prove that $9k=4^n+6n-1$. I ...
1
vote
1answer
59 views

How do I solve this?

Define ${[X_n]}$ by: $X_n = 3, X_{n+1} = {\frac 12} (X_{n-1} + {2\over X_{n-1}})$ a) Show that for any n≥1 we have $X_n$≥ $\sqrt{2}$ b) Show that {$X_n$} is decreasing. c) Deduce from (a) and (b) ...
0
votes
2answers
90 views

Problem with the proof for the Gram-Schmidt orthonormalisation-process

I have an exam coming up next month and I'm trying to understand all the proofs in my book. I got stuck on the Gram-Schmidt proof and would really appreciate some help. I understand everything except ...
3
votes
2answers
100 views

Proof by induction that $3^{4n + 1} + 5^{2n + 1}$ is divisble by $8$

This is a homework problem: Prove that: $$ 3^{4n+1} + 5^{2n+1}$$ is divisible by $8$ for every natural number $n$. Base case: $$n = 0$$ $$ 3^{0 + 1} + 5^{0 + 1} = 8$$ $$8\bmod8 = 0 $$ Base case ...
5
votes
5answers
641 views

Given $n \in \mathbb N$, prove $\sum^n_{k=0}(-1)^k {n \choose k} = 0$

I tried to solve it using induction, but that got me no were, in the middle of the equation stat appearing ks that I don't see how to get out of the equation. I think the easiest way to prove it, it's ...
11
votes
1answer
171 views

A Fantabulous integer is an integer which has another fantabulous integer smaller than it

BdMO 2013 problem-7: A positive integer is called “Fantabulous” if there is another fantabulous positive integer smaller than it. Find the number of fantabulous integers. I am bamboozled at ...
2
votes
4answers
76 views

Prove by induction the following

In the decimal form of the number $3^n$, the second from the end digit is even. My proof so far: Base Case: $n=3$ $3^3=27$. The second from the end digit is even, so the base case is true. ...
0
votes
1answer
67 views

Inductive proof for gcd

Proof that $(\forall n \in \Bbb N)[\gcd(n,(25n+1)^3)=1]$ By the inductive method: $p(n):\gcd(n,(25n+1)^3)=1$ $p(1): \gcd(1,26^3)=1 \implies p(n)\equiv \text{True}$ $p(n): $I assume that $p(n)\equiv ...
1
vote
2answers
189 views

Prove or disprove that every Boolean function can be expressed by using only the operator ↓

I know that the ↓ operator means "nor" but how do I prove/disprove that every Boolean function can be expressed using only this operator ? Induction ? Contradiction ? I have to idea where to begin. ...
1
vote
1answer
60 views

How does $(k+1)!(k+2)-1 = (k+2)!-1$?

I'm trying to do a proof by induction question and I'm at the very last part. Apparently $(k+1)!(k+2)-1 = (k+2)!-1$. I have checked using an online calculator. I don't understand why though.
0
votes
4answers
73 views

Proving $\displaystyle\sum_{k=1}^{m+1} \frac{1}{\sqrt{k}}\gt\sqrt{m+1}$

well the original problem was to prove the sum of k to the negative one half was more that the square root of n but it thought it would be best to use induction and get the equation displayed above. I ...
1
vote
1answer
58 views

Proof by Mathematical Induction [duplicate]

7a. Prove by Mathematical Induction that $4^{n+1}+5^{2n-1}$ is divisible by $21$.
1
vote
1answer
90 views

Proof by contradiction that if a set $A$ contains $n_0$ and contains $k+1$ whenever it contains $k$, then it contains all numbers $\ge n_0$

Prove that if a set $A$ of natural numbers contains $n_0$ and contains $k+1$ whenever it contains $k$, then $A$ contains all natural numbers $\geq n_0$. I have attempted a proof by contradiction ...
1
vote
3answers
143 views

Show by induction : $n^7-n$ is a multiple of 7

I have to prove this : "$n^7-n$ is a multiple of 7". This is what I have done this so far : $P(n):n^7-n$ On putting $n=1,$ $P(1):1^7-1=0$, which is a multiple of 7. So, $P(1)$ is true. Let $P(k)$ be ...
1
vote
2answers
83 views

Induction proof: if $n\in\mathbb{N}$, $f:I_n\to B$, and $f$ is onto, then $B$ is finite and $|B|\le n$

Prove that if $n\in\mathbb{N}$, $f:I_n\to B$, and $f$ is onto, then $B$ is finite and $|B|\le n$. Attempt at a proof: We use induction Base case: When $n=0, I_0=\varnothing$ and since $f$ is ...
1
vote
2answers
72 views

Show by induction $|a_1-a_2+a_3-\ldots \pm a_n| \leq |a_1|$

The assumptions are that $(a_n)$ is a decreasing sequence with $(a_n) \to 0 $, that is all terms are nonnegative. It is easy to see that the subtracted terms are always at least as great as the added ...
0
votes
1answer
77 views

Induction over reals

Would this argument be valid for proving A for all real numbers greater than or equal to a: Prove that A is true at n = a. Assume that A is true for all $ a\le n < k$. Prove that A is true at k. ...
1
vote
4answers
405 views

Prove by induction that $10^n -1$ is divisible by 11 for every even natural number

Prove by induction that $10^n -1$ is divisible by 11 for every even natural number n. $0 \notin N$ Base Case: n = 2, since it is the first even natural number. $10^2 -1 = 99$ which is divisible by ...