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

3
votes
1answer
24 views

Require assistance proving $n≥2 \Longrightarrow \frac{n!}{n^n} ≤ \frac{1}{2}^{\lfloor \frac{n}{2}\rfloor}$

Theorem: $n≥2 \Longrightarrow \frac{n!}{n^n} ≤ \frac{1}{2}^{\lfloor \frac{n}{2}\rfloor}$ Attempted Solution: We use induction. Additionally, we prove the stronger inequality omitting the floor ...
1
vote
2answers
47 views

Proof by induction: $(a+b)^n=a^n+na^{n-1}b+\frac{n(n-1)}{2!}a^{n-2}b^2+…+nab^{n-1}+b^n$

I'm studying in preparation for a Mathematical Analysis I examination and I'm solving past exam exercises. If it's any indicator of difficulty, the exercise is Exercise 1 of 4, part $a$ and graded for ...
0
votes
3answers
46 views

Prove $n^3 + 7n + 3$ is divisible by 3 for all integers n ≥ 0

The statement I'm trying to prove is: $n^3 + 7n + 3$ is divisible by 3 for all integers n ≥ 0 I eventually need to prove $(k + 1)^3 + 7(k + 1) + 3$ is divisible by 3. I don't really understand ...
1
vote
2answers
47 views

Is my proof of the principle of backward induction using well-ordering correct?

I'm trying to prove backward induction, which I'll state as follows: Consider the set $\mathsf{A}$, where $n\in{\mathsf{A}}$, and $m+1\in{\mathsf{A}}$ $\implies$$m\in{\mathsf{A}}$. Then ...
0
votes
0answers
28 views

Problem with induction [on hold]

Prove by induction that given non-negative real numbers $a_1, a_2, a_3, ..., a_n$ ($a_i \ge 0$ for any $i \ge 1$), the folowing inequality is true for $n=1,2,3,...$ $$\prod_{i=1}^n(1 + a_i) \ge 1 + ...
0
votes
0answers
20 views

Solve the Recurrence Relation to Get a Theta Bound

If I have $T(n)=T(n-5)+n$, how would I go about using induction to find a $\Theta$ bound for this. I was able to use a tree method to get that the bounds should be about $\frac{n^2}{5}$, but I am ...
1
vote
1answer
20 views

Proving Multiplicity in Polynomials with derivatives.

After learning multiplicity in polynomials we were given the task of proving that: if $ f(\alpha) = f'(\alpha) = f''(\alpha) = f'''(\alpha) =$ .... $f^{k-1}(\alpha) = 0$ and $f^{k}(\alpha) \not= 0$ ...
1
vote
4answers
48 views

Show that for each $n \geq 2$, $\left(1 - \frac{1}{4}\right)\left(1 - \frac{1}{9}\right) \cdots \left(1 - \frac{1}{n^2}\right) = \frac{n + 1}{2n}$ [duplicate]

Need to show that for each $n \in \mathbb{N}$, with $n \geq 2$, $$\left(1 - \frac{1}{4}\right)\left(1 - \frac{1}{9}\right) \cdots \left(1 - \frac{1}{n^2}\right) = \frac{n + 1}{2n}$$ How to start the ...
1
vote
1answer
25 views

How does this result follow?

In my real analysis text, an example of proof by induction is given by proving that for any real $x\ge 0$ and all integers $n\ge 0$ $$(1+x)^n \ge 1+nx+\frac {n(n-1)}2x^2$$ I can follow and understand ...
0
votes
3answers
26 views

The basis step is confusing, Prove by mathematical induction that $3 | (n^3 - n)$ for every positive integer n.

So I have an answer.. but the basis step doesn't make any sense to me. It is possible that I do not understand the syntax used. Let $P(n)$ be the predicate $3 | (n^3 - n)$ for every positive ...
-5
votes
2answers
43 views

Mathematical induction - divisibility by 17 [on hold]

I am really stuck with this next task and I would appreciate help. It would be great if I got a whole procedure and explanation of it. $$17|(3\cdot5^{2n+1}+2^{3n+1})$$ Thank you for your time and ...
0
votes
1answer
29 views

Is This Mathematical Induction?

Mathematical induction Follows Thus: $1.$ The basis (base case): prove that the statement holds for the first natural number $n$. Usually, $n = 0$ or $n = 1$. $2.$ The inductive step: prove that, ...
0
votes
3answers
32 views

Prove by induction that $36,306,3006,30006$ is divisible by 18

Hi I'm quite new to induction so I don't really know how I should tackle this problem. I took out a calculator and checked the results 2,16,167,1667 I sort of see a pattern but how would I start the ...
1
vote
0answers
30 views

Regarding the number of isomorphisms between splitting fields

Let $\phi : F \rightarrow F_1$ be an isomophism of fields and $f(x) > \in F[x]$. Let $\Phi : F[x] \rightarrow F_1[x]$ be the unique ring isomorphism which extends $\phi$ and maps $x$ to ...
1
vote
1answer
17 views

Inductive factorial formula proof - can't figure out how to finish proof

I am reading The Algorithm Design Manual and in the induction section of the first chapter, I am struggling to figure out how you go from one line to another in the final proof. Here is a picture of ...
6
votes
1answer
76 views

A Increasing Multiplicative Functional Equation where $nm$ is a cube

Let $f:\mathbb{N}\rightarrow\mathbb{N}$ be a strictly increasing function such that $$f(2)=2$$ and $$f(mn)=f(m)f(n)$$ for all positive integers $m,n$ such that $mn$ is a perfect cube. ...
0
votes
1answer
21 views

Prove the arithmetic-geometric inequality for integers $n$ that are powers of two, i.e. $n=2^k$.

Prove the AG inequality for integers $n$ that are powers of two, i.e. $n=2^k$. Suppose $a_1,a_2,\dots,a_n>0$. The arithmetic mean of these numbers is $$\frac{a_1+\dots+a_n}{n}.$$ The geometric ...
0
votes
2answers
38 views

Proof by induction for recursive sequence with no explicit formula.

The problem I am trying to solve is: "show that the sequence defined by $a_1=6$ and $a_{n+1}=\sqrt{6+a_n}$ for $n\ge 1$ is convergent, and find the limit." So I know that I need to use proof by ...
0
votes
0answers
22 views

How to make inductive step for a Fibonacci proof [duplicate]

I have to prove $F^2_{n−1} = F^2_n + F^2_{n−1}$ for any $n >=1$ by induction (for the Fibonacci sequence). For the basis step, I have: $n = 1; $ $F_{(1)-1} = F^2_{(1)} + F^2_{(1)-1} ->$ $ ...
1
vote
4answers
58 views

Prove that $f(n) = 3n^5 + 5n^3 + 7n$ is divisible by 15 for every integer $n$

So far I have only been able to complete the base case for which I got the following: $$f(n) = 3n^5 + 5n^3 + 7n$$ $$f(n) = 3(1)^5 = 5(1)^3 + 7(1)$$ $$f(n) = 3 + 5 + 7$$ $$15/15 = 1$$ From here ...
0
votes
1answer
37 views

'Mathematical Induction'

Use mathematical induction to prove that $4^n -3^n + 1 = 7a_{n-1} – 12a_{n-2} + 6$ with $n \ge 3$ with the initial condition $a_1 = 2$ and $a_2 = 8$ . Given that $a_n = 4^n -3^n + 1$. I am confused ...
2
votes
1answer
80 views

Matrix induction proof

Given the following $\lambda_{1}=\frac{1-\sqrt{5}}{2}$ and $\lambda_{2}=\frac{1+\sqrt{5}}{2}$ How do I prove this using induction: $\begin{align*} A^k=\frac{1}{\sqrt{5}}\left(\begin{array}{cc} ...
0
votes
1answer
90 views

Proving by induction that a balanced strings of parentheses has equally many opening and closing parentheses

In computer science, a string is a finite sequence of characters. For strings $A$ and $B$, we express $AB$ as $A$ followed by $B$. A balanced string of parentheses is a string of open and closed ...
0
votes
2answers
51 views

Prove $\log(x)^{10} < x$ (for $x > 10^{10}$)

I need to prove that $\log(x)^{10} < x$ for $\ x>10^{10}$ It's pretty clearly true to me, but I need a good proof of it. I tried induction, and got stuck there.
3
votes
4answers
55 views

induction to prove the equation $3 + 9 + 15 + … + (6n - 3) = 3n^2$

I have a series that I need to prove with induction. So far I have 2 approaches, though I'm not sure either are correct. $$3 + 9 + 15 + ... + (6n - 3) = 3n^2$$ 1st attempt: \begin{align*} & = ...
-6
votes
1answer
42 views

Prove by induction: $\sum _{i=1} ^n \frac 1 {i(i+1)} = \frac n {n+1}$ [closed]

Any theory of computation guys here to help? This is not my subject so i have no idea about this, the question is, 1. Prove by induction:$$\sum _{i=1} ^n \frac 1 {i(i+1)} = \frac n {n+1}$$ 2. ...
0
votes
2answers
37 views

Proof by induction to prove an inequality help?

Prove by induction on m where m is an integer, such that m ≥ 2: $$Pm:=\sum_{n=1}^{m} \frac{1}{\sqrt{n}} < 2\sqrt{m}-1$$ I know this holds for the base case since when m=2, P2 is: ...
0
votes
0answers
21 views

Formula for sum of first k positive integers divisible by m [closed]

Find a formula for the first k positive integers divisible by an integer m. Use induction to prove it.
1
vote
2answers
25 views

Induction with binomial coefficient

Is mathematical Induction possible with this sigma sign? $A(k) =\sum_{j=0}^{k} \binom{m}{j}\binom{n}{k-j} = \binom{m+n}{k}$ $A(k+1) = \sum_{j=0}^{k+1} \binom{m}{j}\binom{n}{(k+1)-j} = ...
0
votes
0answers
11 views

Show that $|c_k|\le \frac{C(C+\lambda/r)(C+2\lambda/r)\dots(C+(k-1)\lambda/r)}{k!},\,k\ge1$

Given a power series $p(t) = \sum_{k=0}^\infty a_kt^k$ with radius of convergence $R \in (0,\infty]$, consider the initial-value problem $y' = p(t)y, \,\,\,y(0) = 1$. Substituting $y(t) = ...
0
votes
2answers
30 views

Prove that for all $n \gt 1$ $\lim_{r \to 1} \frac {r^n-1}{r-1} = n$

Prove that for all numbers $n \gt 1$ $\lim_{r \to 1} \frac {r^n-1}{r-1} = n$ I think induction will work for this, but I can't seem to figure it out. I have the base $n=1$ case because $\lim_{r \to ...
2
votes
2answers
54 views

Prove $\frac{1\cdot 3\cdots(2n-1)}{2\cdot 4 \cdots(2n)}<\frac{1}{\sqrt{2n+1}}$, $n\ge 1$

Prove $\frac{1\cdot 3\cdots(2n-1)}{2\cdot 4 \cdots(2n)}<\frac{1}{\sqrt{2n+1}}$, $n\ge 1$. I begin by letting $n=1$ then $\frac{1}{2}<\frac{1}{\sqrt{3}}$. Then assume $\frac{1\cdot ...
0
votes
1answer
33 views

Standard proof of permutations of $n$ people standing in line

I want to prove the statement: For $n$ people the number of permutations is $n!$. How to prove or justify this statement ? I think the easiest way is to use induction. If we have a line of $1$ ...
1
vote
3answers
89 views

Suppose $a \in \mathbb{Z}.$ Prove that $5 \mid 2^na$ implies $5 \mid a$ for any $n \in \mathbb{N}$

This question is supposed to be solved by induction, however I'm unsure of where to get my base case from exactly, because the question is asking about both $a$ and $n$. I started with my base case ...
0
votes
1answer
38 views

Proof strategy for propositional logic algorithm

I have to proof the following theorem: Proof that $\eta_1 \vee \eta_2 \equiv DISTR(\eta_1, \eta_2)$. The algorithm DISTR($\eta_1, \eta_2$) is the following: Now I want to use induction to ...
0
votes
1answer
28 views

proving $E \leq \frac{(n-k+1) \cdot (n-k)}{2}$

I'm trying to prove something about graph theory, but I'm not sure if I'm thinking in the right direction. Let $G$ be a simple graph, that is a graph without multiple edges and loops, let $n$ be the ...
0
votes
3answers
53 views

Prove that: $2^n < n!$ Using Induction

I'm told to show that $2^n < n!$ using induction This is my attempt at it: BC: $n=4, 2^4 = 16 < 4!$ IH: n = k, $2^k < k!$ IS: try n = k+1 I'm told to only work from one side, so I try ...
2
votes
1answer
39 views

Prove: $ 1\times3 +2\times4 + \cdots + n(n+2) = \frac{1}{6} \times n(n+1)(2n+7)$ using Induction

I'm told to prove this by Mathematical Induction: $ 1\times3 +2\times4 + \cdots + n(n+2) = \frac{1}{6} \times n(n+1)(2n+7)$ This is what I have so far: BC: Try $n=1$: $ 1\times3 +2\times4 + \cdots ...
3
votes
3answers
77 views

Induction proof: $(x_{1}+x_{2}+…+x_{n})^2\leqslant n(x_{1}^2+x_{2}^2+…+x_{n}^2)$ [duplicate]

I have a problem proving this inequality but I can't get anywhere after the inductive step. $$(x_{1}+x_{2}+...+x_{n})^2\leqslant n(x_{1}^2+x_{2}^2+...+x_{n}^2)$$ Maybe some hints would help.
1
vote
1answer
39 views

Have some trouble proving $(1-x)^n \geq 1-nx$

Here is the question: Prove that $(1-x)^n \geq 1-nx,~\forall n\in\mathbb{N}~and~x\in(0,1)$. My proof by induction: Base Case: when $n=1$, $(1-x)^1\geq 1-1\cdot x$ Induction Hypothesis: $\forall i \in ...
1
vote
2answers
41 views

Can the Recursion Theorem be proved in Peano Arithmetic?

A recursive function on $\mathbb{N}$ can be defined as follows: Given an element $a \in \mathbb{N}$ and a function $f:\mathbb{N}\rightarrow\mathbb{N}$, we can define a function ...
0
votes
1answer
33 views

Factorial and induction

Part of step in induction: $(2 k+1)*((1*3* 5*\dotsb* (2k-1)) =1*3*5*\dotsb*(2k+1)$ Am I correct with believing that we in first instance went up to $k$, and then we went further to $2((k+1)-1$ hence ...
1
vote
1answer
58 views

Proof of product summation of binomial coefficients

when I try to proof the sum of two independent negative binomial distribution to be negative binomial, I end up with how to proof the following identity. I try the induction but after I rearrange the ...
0
votes
1answer
20 views

Induction on String? (automata related)

Honestly, all I know about mathematical induction is as follow: prove $P(0)$ - base step for all $n \ge 1$, prove $(P(n − 1) \rightarrow P(n))$ - inductive step Prove the following claim by ...
3
votes
1answer
35 views

Can I extend mathematical induction to real numbers? [duplicate]

Here is my rather simple idea. I will treat the set of real numbers as a set of discrete continuities, each separated by an Epsilon ball that tends to 0. So, let's say P(b) is true. We then assume ...
0
votes
0answers
14 views

Induction to find string length equivalence

Rewrite system of RRR ≡ NULL, FF ≡ NULL, RRF ≡ FR. Show that each string in {F,R}* is equiv. to one of the six strings: NULL, R, RR, F, FR, FRR. A hint is to use induction and ask if every string of ...
0
votes
1answer
20 views

Show that $U_{n+1}-1<1/2(U_n-1)$

Given that U_0=3/2 $U_{n+1}=U_n^2-2U_n+2$ Show that $1<U_n<=3/2$ I did it by induction Then we have to show that $U_{n+1}-1<1/2(U_n-1)$ And deduce that $U_n-1<=(1/2)^{n+1}$ Then we ...
2
votes
1answer
45 views

Use induction to prove that any (finite) list is a permutation of itself—in other words, that the permutation relation is reflexive.

I'm having a bit of trouble with starting this proof by induction. I'm given that the definition of a permutation is: List a is a permutation of list b if any of the following are true: • list a and ...
1
vote
0answers
38 views

How do you express $\sum_{j=1}^{n} j^{k+1}$ in terms of $\sum_{j=1}^{n} j^{k}$?

I am trying to use induction to prove, for every positive integer $k$, that $$\sum_{j=1}^{n} {j^{k}} = \frac{n^{k+1}}{k+1} +\frac{n^k}{2} + P_{k-1}(n)$$ where $P_{k-1}$ is a polynomial of degree at ...
0
votes
1answer
62 views

Use Induction to prove that for all $n \in \mathbb{N}, (x^n + \frac{1}{x^n}) \in \mathbb{Z}$ if $x+\frac{1}{x}\in\mathbb{Z}$.

Assume $x \in \mathbb{R}$ and $(x + \frac{1}{x}) \in \mathbb{Z}$. Use Induction to prove that for all $n \in \mathbb{N},~ (x^n + \frac{1}{x^n}) \in \mathbb{Z}$. I'm not sure how to use the ...