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

0
votes
1answer
100 views

Which natural numbers satisfies $n^2<2^n$ and why? using mathematical induction [duplicate]

Which natural numbers satisfies $n^2<2^n$ and why? using mathematical induction
0
votes
2answers
71 views

How $x^2$ increases by $x+1/x$? [duplicate]

I was going through one of the topic "Introduction to Formal proof". In one example while explaining "Hypothesis" and "conclusion" got confused. The example is as follows: If $x\geq4$, then $2^x ...
1
vote
1answer
96 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
159 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
347 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
278 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
918 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
56 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
83 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
54 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
2k 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
542 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
37 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 ...
0
votes
1answer
73 views

How do i prove $\text{F}_\text{n+1}^2 - F_n\text{F}_\text{n+2} = (-1)^n$ by induction? [duplicate]

$F_n$ refers to the $n$ term of the Fibonacci Sequence. I think i'm suppose 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
63 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
113 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
180 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
178 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
103 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
99 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
45 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
124 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
45 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
123 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
239 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
385 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
85 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
3answers
574 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
170 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
63 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
183 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
57 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
89 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
136 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
77 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 ...