Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [induction]

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

1
vote
3answers
53 views

Prove $\frac{2^{4n}-(-1)^n}{17} \in \mathbb{N}$ by induction

Here is my attempted proof: $\forall n \in \mathbb{N}$, let $S_n$ be the statement: $\frac{2^{4n}-(-1)^n}{17} \in \mathbb{N}$ Base case: $S_1$: $\frac{2^{4(1)}-(-1)^1}{17} = \frac{16+1}{17} = 1 \in \...
0
votes
2answers
30 views

Given a finite collection of numbers, the products obtained by multiplying them in any order are all equal.

How do I use induction to prove the following for $n\geq 3$ ($n$ is the number of numbers in the finite collection)? 1) Given a finite collection of numbers, the products obtained by multiplying them ...
0
votes
1answer
22 views

How to solve propositional logic problems by induction

I'm trying to solve a bunch of problems like this one and every time I get stuck. So I don't need an actual solution but to understand how you solve this kind of problems. I know they're usually ...
0
votes
1answer
39 views

Proof by induction help $\sum_{i=1}^n i2^i$

After looking at the response, the formula would be $S_n = n2^{n+2} - (n+1)2^{n+1} + 2$ How would i use induction to prove this formula? I tried setting $S_{n+1}$ but having hard time getting $S_{n+...
0
votes
0answers
17 views

Mathematical Induction and subsets

Mathematical Induction is a technique used to prove statements that apply to a set S, where S is a subset of the nonnegative integers. To what types of sets would one apply generalized induction?
1
vote
3answers
32 views

Proof request: If a function satisfies a polynomial recurrence then it is a polynomial

Suppose we would like to find a formula for some interesting real-valued function on the positive integers $f(n):\mathbb{Z}^+\rightarrow\mathbb{R}$, and we have the inductive equation $$\forall n\in\...
2
votes
1answer
38 views

Proving a binomial coefficient inequality per induction

$\left(\begin{array}{c}2n\\ n+k\end{array}\right) < \left(\begin{array}{c}2n\\ n\end{array}\right), n,k \in \mathbb{N}, 1\leq k \leq n$ Proving this by induction on $k$ is no problem. However, I ...
2
votes
0answers
29 views

Induction on Fibonacci numbers

For a homework problem, I need to prove $f_0f_1+f_1f_2+...+f_{2n-1}f_{2n}=f_{2n}^2$ for $n\geq1$ with induction. So far, using my basis step, I have $$\sum_{i=1}^{k+1} f_{2(k+1)-1}f_{2(k+1)}=$$ $$\...
0
votes
0answers
38 views

Prove that $\frac {2n-1}{2} - \frac {2n-2}{3} + … - \frac 2{2n-1} + \frac 1{2n}=\frac1{n+1} + \frac3{n+2}+…+\frac{2n-1}{2n}$

Prove that $\frac {2n-1}{2} - \frac {2n-2}{3} + ... - \frac 2{2n-1} + \frac 1{2n}=\frac1{n+1} + \frac3{n+2}+...+\frac{2n-1}{2n}$ for all $n \in \mathbb{Z^+}$ This question for me was pretty confusing ...
-2
votes
0answers
20 views

Prove by induction this statement

I need to prove by induction the following statement. Given $a_n$ with $n\in\mathbb{N}$ and $b>1$. $a_n$ is a sequence in $ \mathbb{N}$ If $\forall n \in \mathbb{N}$ $ a_n<b \Rightarrow \...
1
vote
2answers
42 views

To prove $\tan \phi_m + \sec \phi_m =(\tan \phi_1 + \sec \phi_1)^m $

If $\phi_1, \phi_2, ... $ is a series of positive acute angles so that $\tan \phi_{m+1} = \tan \phi_m \sec \phi_1 + \sec \phi_m \tan \phi_1$ then prove that- $$\tan \phi_{m+n} = \tan \phi_m \sec \...
3
votes
1answer
21 views

Induction: How to prove each number can be written as sum of natural numbers such that sum of inverses of these numbers will be 1.

For every $n>32$, prove that $n$ can be written as sum of a number of natural numbers such that sum of inverses of these numbers will be 1. Suppose the statement is correct for $33, 34, ..., 73$. ...
0
votes
5answers
76 views

How do I prove that $\sqrt 5 + \sqrt 7$ irrational?

I got stuck at : $a^2/b^2 = 12+2 \sqrt 35$ I understand that $12$ is rational and now I need to prove that $\sqrt{35}$ is irrational. so I defined $∀c,d∈R$ while $d$ isn't $0$ that: $c^2/d^2 = \...
1
vote
3answers
85 views

Induction proof: $\frac{1}{2^1} + \frac{2}{2^2} + \frac{3}{2^3} +…+\frac{n}{2^n}$ $<2$ [duplicate]

Prove by induction the following. $$\frac{1}{2^1} + \frac{2}{2^2} + \frac{3}{2^3} +\dots+\frac{n}{2^n}<2.$$ Caveat: The $<$ will be hard to work with directly. Instead, the equation above can ...
2
votes
1answer
26 views

Is this induction proof mathematically correct?

Proof that $\frac{n^3}{3} < 3n-3$ is true for $n=2$ but false for every other $ n \in \mathbb{N}$. Idea is to proof that $\frac{n^3}{3} \geq 3n-3$. Let $n$ be $n=3$ $\frac{27}{3} \geq 9-3 $. ...
-1
votes
4answers
54 views

How to prove the following inequality $\sqrt n {2n\choose n}<2^{2n-\frac{1}{2}} \,n\in \mathbb{N}$? [on hold]

How to prove the following inequality? $$\sqrt n {2n\choose n}<2^{2n-\frac{1}{2}} \quad n\in \mathbb{N}$$ I tried to prove it by using mathematical induction, but I still get contradiction
1
vote
3answers
56 views

use induction to prove that $\sum_{k=1}^{n} k(k + 1) = \frac{n(n + 1)(n + 2)}{3}$ for all $n ∈ N$.

I am supposed to use induction to prove that $$\sum_{k=1}^n k(k+1) = \frac{n(n + 1)(n + 2)}{3}$$ for all $n \in \mathbb{N}$. I am confused on how to go about this question, a step by step guide of ...
3
votes
5answers
69 views

Show that $n^n>(n+1)!$ for all $n\ge3$

Show that $n^n>(n+1)!$ for all $n\ge3$ For $n=3$ it is to prove. assumed it true for some fixed $n\in \mathbb{N}$. Then tried to prove for $n+1$ $(n+1)^{n+1}=(n+1)^n(n+1)>n^n(n+1)>(n+1)!(n+...
0
votes
2answers
16 views

Help proving inequality by induction with recurrent sequence?

Problem For a sequence, $u_n$ , $u_1=u_2=1$ and $u_{n+2}=u_{n+1}+u_n$ Using induction, prove $u_n<2^n$ So, I'm having trouble working through this. I've tried coming up with a conjecture for $...
5
votes
2answers
74 views

Prove $ \frac{d^n}{dx^n}\ln(x)=\frac{(n-1)!(-1)^{n-1}}{x^n} $ by induction

Prove $$ \frac{d^n}{dx^n}\ln(x)=\frac{(n-1)!(-1)^{n-1}}{x^n} $$ by induction. Attempt to solve Base case $n=1$ $$ \frac{d}{dx}\ln(x)=\frac{(1-1)!(-1)^{1-1}}{x^{1}}=\frac{1}{x} $$ which is ...
0
votes
2answers
43 views

Prove by induction $n! > n^2$ for $n \geq 4$

This theorem is supposed to be true for $n \geq 4$ I’ve tried $n!(n+1) > n^2(n+1) $ Not sure where to go from here or if I’m on the right track
1
vote
1answer
32 views

Induction: Prove all numbers in the range $(0, n)$ can be generated

Two positive coprime natural integers $n,m$ and $0$ are given. at each step we can add the average of two given numbers to the set, if they are both odd or both even. Prove that this way you can ...
3
votes
4answers
62 views

Induction: How to prove that $ab^n+cn+d$ is divisible by $m$.

If $a+d$, $(b-1)c$, $ab-a+c$ are divisible by $m$, prove that $ab^n+cn+d$ is also divisible by $m$. I want to prove this by induction. For proving $ab^{k+1}+c(k+1)+d$ is divisible by $m$, i want to ...
2
votes
1answer
55 views

$F(X)=\lbrace 3\rbrace\cup\lbrace x+3|x\in X\rbrace$ show that $F$ is continous and cocontinous

Let $U$ denote the set of natural numbers and let $F: P(U) \rightarrow{P(U)}$ denote the function given by $F(X) = \{3\} \cup \{x + 3 | x \in X\}$ a) show that $F$ is continous and cocontinous b) ...
2
votes
6answers
57 views

Prove that $7^n+2$ is divisible by $3$ for all $n ∈ \mathbb{N}$

Use mathematical induction to prove that $7^{n} +2$ is divisible by $3$ for all $n ∈ \mathbb{N}$. I've tried to do it as follow. If $n = 1$ then $9/3 = 3$. Assume it is true when $n = p$. ...
0
votes
1answer
42 views

prove that $b$ balls can be placed in $\binom{n-b+1}{b}$ spaces without touching

There are several questions (like this one) that involve counting the ways that $b$ balls can be placed into $n$ spaces such that no balls are adjacent, for instance $B\_ B\_ B\_ $ but not $ BB\_ B\_\,...
4
votes
5answers
113 views

Prove that $3\cdot 5^{2n+1} +2^{3n+1}$ is divisible by $17$ for all $n ∈ \mathbb{N}$

Use mathematical induction to prove that $3\cdot 5^{2n+1} +2^{3n+1}$ is divisible by $17$ for all $n ∈ \mathbb{N}$. I've tried to do it as follow. If $n = 1$ then $392/17 = 23$. Assume it is ...
1
vote
0answers
10 views

Prove that for any odd number m, there is some $e \in \mathcal{E}$ such that $vr(e) + op(e) = m$

Prove that for any odd number m, there is some $e \in \mathcal{E}$ such that $vr(e) + op(e) = m$ vr means variable, op means operators like $+/-$ Attempt: I will prove this with structural ...
0
votes
1answer
19 views

Unsure how to do this problem with iteration and mathematical induction

So I have this question where I have to find the explicit formula using iteration, and then simplify that formula and use mathematical induction to prove it. I'm really not good at this, and our ...
0
votes
1answer
17 views

Induction in which the base case is not 0

Suppose that $ n\in\mathbb{N}$ with $n\neq0$. Show that $0\in n$. (Hint: if the set $X$ satisfies Peano's axioms, then every $x\in X$, other than $0_x$, is $S(y)$ for some $y\in x$. Also use induction....
0
votes
1answer
22 views

Strong induction with recursive definition function

Look at following recursive function definition for function $F :\mathbb{N}​\times\mathbb{N}​ \to \mathbb{N}$​: $$ \begin{split} F(x,0) & = 0\\ F(x,n) & = x + F(x, n-1) \end{split} $$ Prove ...
1
vote
2answers
27 views

Iteration to guess formula and simplify and use mathematical induction to prove right

I have this homework question, but my teacher didn't explain how to do these kind of problems too well. So basically the question is, Use iteration to guess an explicit formula for the sequence, then ...
0
votes
2answers
18 views

By M.I prove that? [closed]

$(2n)! < 2^{2n} (n!)^2$; How to prove this by mathematical induction ?
0
votes
1answer
36 views

By mathematical induction prove that? [duplicate]

$\frac{1}{n + 1} + \frac{1}{n + 2} + \frac{1}{n + 3} + ..... +\frac{1}{3(n) + 1} > 1 $; Here in this sequence after checking the basis for n = 1 , i.e $\frac{1}{4} > 1$, Which cannot be true; ...
-1
votes
0answers
8 views

Prove by induction the feature:

If m,n are Natural Numbers, and $\frac{m^2}{n^2}<2$ prove by induction: $0<\frac{(m+2n)^2}{(m+n)^2}-2<2-\frac{m^2}{n^2}$ Step 1 To prove: $0<\frac{(m+2n)^2}{(m+n)^2}-2$ So: $0<\...
-3
votes
0answers
38 views

Solve the recurrence relation $T(n) = (n-1) T(n-1)$

How do I resolve the following recurrence relation? $T(n) = (n-1) T(n-1),$ $T(1) = 1.$ My reasoning: $T(n) = T(n-1-k)(n-1)(n-2)(n-3)\cdots(n-k)$ $k = n$ $\leftarrow$ yields the ...
0
votes
0answers
63 views

State this property in completely formal notation with quantifiers. [closed]

Consider the property that whenever n is an odd positive integer, n^2 − 1 is divisible by 8. State this property in completely formal notation with quantifiers.
-2
votes
1answer
27 views

Show by induction that $(\frac{n}{3})^n \leq \frac{n!}{3}$

Show by induction that $(\frac{n}{3})^n \leq \frac{n!}{3}$ In oder to prove that, I must prove that $(\frac{n+1}{3})^{n+1} \leq \frac{(n+1)!}{3}$ But how can i show that?
0
votes
0answers
14 views

recursive program correctness proof for $n^2$

let $k \in \mathbb N$, we define the predicate $Q(k)$ as follows $Q(k)$ let $n \in \mathbb N$ and let $k = n$, then $SQUARE(n)$ terminates and returns $n^2$ Will use pci to prove Base Case: let $k =...
2
votes
2answers
56 views

$\sum\limits_{k=1}^nk^r = \frac{1}{1+r}n^{r+1}+a_rn^r +…+a_1n$

Show that for every $r \in \mathbb{N}$ there are numbers $a_1,..,a_r \in \mathbb{Q}$ such that $\sum\limits_{k=1}^nk^r = \frac{1}{1+r}n^{r+1}+a_rn^r +....+a_1n$ for all $n \in \mathbb{N}$ There ...
1
vote
3answers
34 views

Proof by Induction of $\frac{d^n}{dx^n} (\ln(x))$ = $\frac{(-1)^{n-1}(n-1)!}{x^n}$ for $n\geq1$. [duplicate]

Conjecture for $\ln(x)$ and $\frac{d^ny}{dx^n}$ showed how to find the conjecture for $ln(x)$ after testing multiple values. For this question that I have, I have to prove using induction that $$\...
0
votes
2answers
48 views

Conjecture for $\ln(x)$ and $\frac{d^ny}{dx^n}$

I'm not really sure where to start, I found the first, second, third and fourth derivatives of $\ln(x)$ to be $\frac{1}{x}$,-$\frac{1}{x^2}$, $\frac{2}{x^3}$, and -$\frac{6}{x^4}$, respectively. ...
0
votes
2answers
35 views

Induction Proof ${n}\geq 3, (1+\frac{1}{n})^{n}\lt n$

For each natural number $n$ with ${n}\geq 3, (1+\frac{1}{n})^{n}\lt n$. So far, I've tested the claim for $n=3$, which was true. Then, I stated that I need to show that $(1+\frac{1}{n+1})^{n+1} \lt n+...
2
votes
1answer
45 views

Divisibility Proof $8^n|(4n)!$

Is the following proposition true or false? Justify your conclusion. For each non-negative integer $n$, $8^n|(4n)!$. Attempt: I've tried to expand $(4(n+1))!$ to show that it's equivalent to $(4n+...
0
votes
1answer
45 views

What's wrong with this induction? (Runtime analysis of standard polynomial long division)

In my studies for my Bachelor's thesis, I've gone through a runtime analysis of plain vanilla polynomial long division, i.e. I wanted to prove the statement: Let $f,\,g \in F[X] \land g\neq 0$ where $...
0
votes
1answer
29 views

Proving recursive inequality with strong induction

Suppose $h_0, h_1, h_2, \dots$ is a sequence defined: $\qquad h_0=1, h_1=2, h_2=3$ $\qquad h_k=h_{k-1}+h_{k-2}+h_{k-3}, \forall k \in \mathbb{Z}\wedge k\ge 3$ Prove that $h_n \le 3^n,\forall n \in \...
1
vote
1answer
24 views

Recursive program correctness proof of a simple python program that returns (x + y).

For $k \in \mathbb N$ we define $Q(k)$ as follows $Q(k): $ let $x, y \in \mathbb N$ and $x$ is a multiple of $3$ and $k = x + y$, then $FUN(x, y)$ terminates and returns $x + y$ I will prove $Q(k)$ ...
-1
votes
1answer
37 views

Prove by induction… With exponent and factorial [closed]

Could someone please help me to prove this by induction? $$ \left(1+\frac{1}{1}\right) ^1\cdot \left( 1+\frac{1}{2}\right)^2\cdot...\cdot\left( 1+\frac{1}{n-1}\right)^{n-1}=\frac{n^n}{n!}, $$ for $...
1
vote
1answer
41 views

Prove by induction that $W_n = F_{2n+2}$

My problem relies on an earlier recursive definition that we solved in class: $W_n = 3W_{n-1}- W_{n-2}$ if $n \ge 2, W_0=1$, and $W_1=3.$ It also recalls the Fibonacci recursive definition of $F_n = ...
2
votes
2answers
64 views

show that $\frac{1}{3n+1}+\frac{1}{3n+2}+…+\frac{1}{5n}+\frac{1}{5n+1} < \frac{2}{3}$ , $\forall n \mathbb \in{N}$ [closed]

Show that $$\frac{1}{3n+1}+\frac{1}{3n+2}+...+\frac{1}{5n}+\frac{1}{5n+1} < \frac{2}{3}$$ for all $n \in \Bbb{N}$ I tried with induction method but I can not find any results.