Induction in general is the inference from the particular to the general. Mathematical induction is not true induction, but is a form of deductive reasoning. Its most common use is induction over well ordered sets, such as natural numbers, or ordinals. While induction can be expanded to class ...

learn more… | top users | synonyms

0
votes
1answer
25 views

Proving sequence statement using mathematical induction, $d_n = \frac{2}{n!}$

I'm stuck on this homework problem. I must prove the statement using mathematical induction Given: A sequence $d_1, d_2, d_3, ...$ is defined by letting $d_1 = 2$ and for all integers k $\ge$ 2. $$ ...
0
votes
1answer
21 views

Prove summation by Induction

Prove this by induction n ∑ i(i!) = (n+1)!-1 i=1 So I wrote: ...
3
votes
1answer
67 views

Mathematical induction--When it can and can't be used

I'm working through a problem set on mathematical induction. One of the problems asks you to prove that for all $n\in\mathbb N$, $$\sum_{i=0}^{n}8n-5=4n^2-n.$$ I don't have a problem proving this, ...
2
votes
2answers
55 views

Some rather non-traditional forms of mathematical induction.

The definition of induction that most of us are familiar with is this: If statement $S$ is true for $1$, and $$S \text{ is true for } n\implies S \text{ is true for }n^+$$ then $S$ is true for all ...
6
votes
1answer
36 views

How to prove an inequality

$a$, $b$, $c$, $d$ are rational numbers and all $> 0$. $\max \left\{\dfrac{a}{b} , \dfrac{c}{d}\right\} \geq \dfrac{a+c}{b+d}\geq \min \left\{\dfrac{a}{b} , \dfrac{c}{d}\right\}$ Hope someone ...
1
vote
1answer
29 views

Discrete Math Induction: $\sum^n_{i=1} \frac1{i(i+1)}$ [duplicate]

For $\sum^n_{i=1} \frac1{i(i+1)}$ Find a formula and proofs that it holds for all n ≥ 1. How would I find the formula for this one that can hold for all n ≥ 1?
-1
votes
2answers
49 views

Discrete Math On Induction proof: $\sum_{i=1}^n n2^n = (n-1)2^{n+1} + 2$ [duplicate]

Show by induction that the following formulas hold. $\sum_{i=1}^n n2ⁿ = (n-1)2^{n+1} + 2$ What did a similar problem to this but this one is a little different. I think is because this one has a ...
0
votes
3answers
59 views

If $a$ and $b$ are relatively prime then so are $a$ and $b^n$ for every positive integer $n$

I have been asked to prove the following via induction (as the textbook as suggested): If $a$ and $b$ are relatively prime then so are $a$ and $b^n$ for every positive integer $n$ So, I did the ...
-1
votes
1answer
90 views

Use Mathematical Induction to prove that $\frac{1}{1 \cdot 2} + \frac{1}{2 \cdot 3} +…+\frac{1}{n(n+1)}=1-\frac{1}{n+1}$

Use Mathematical induction to prove that for all integers, $n$ is greater than or equal to $1$. I am confused on what to do after I do the the basis step that is using $n$ as $1$. $$\frac{1}{1 \cdot ...
0
votes
3answers
152 views

Prove that $\log(x) < x$ for $x > 0$, $x\in \mathbb{N}$.

I'm trying to prove $ \log(x) < x$ for $x > 0$ by induction. Base case: $x = 1$ $\log (1) < 1$ ---> $0 < 1$ which is certainly true. Inductive hypothesis: Assume $x = k$ ---> $\log(k) ...
0
votes
1answer
25 views

Prove uniqueness of recursive function

I am currently reading Cutland's Computability and would like to figure out how to solve Theorem 4.2 which states: Let $x=(x_1 \dotsc x_n)$, and suppose that $f(x)$ and $g(x,y,z)$ are functions; ...
0
votes
1answer
24 views

$lcm(a_{1},…,a_{n})=lcm(lcm(a_{1},…,a_{n-1}),a_{n})$

I tried to prove this by complete induction on $n$ but I am having problems in the inductive step: Suppose $$lcm(a_{1},...,a_{n})=lcm(lcm(a_{1},...,a_{n-1}),a_{n}) \forall k\le n\in \mathbb ...
0
votes
3answers
47 views

Prove that $\sum \frac{1}{2^n} = 1- \frac{1}{2^n}$ [closed]

Prove that $$\Large\sum\limits_{k=1}^n \frac{1}{2^k} = 1 - \frac{1}{2^n}$$ for all $n$. I am apparent not good enough at algebra for this one.
6
votes
0answers
65 views

My first proof that uses the well-ordering principle (very simple number theory). Please mark/grade.

What do you think about my first proof that uses the well-ordering principle? Please mark/grade. Theorem The sum of the cubes of three consecutive natural numbers is a multiple of 9. Proof ...
0
votes
2answers
19 views

Let $A_1, A_2, \ldots, A_n$ be sets (where $n \ge 2$). Suppose for any two sets $A_i$ and $A_j$ either $A_i \subseteq A_j$ or $A_j \subseteq A_i$

Let $A_1, A_2, \ldots, A_n$ be sets (where $n \ge 2$). Suppose for any two sets $A_i$ and $A_j$ either $A_i \subseteq A_j$ or $A_j \subseteq A_i$. Prove by induction that one of these $n$sets is a ...
1
vote
2answers
71 views

Prove by induction $1 + \frac{1}{2} + \frac{1}{2} + \frac{1}{3} + \ldots + \frac{1}{2^n} \ge 1 + \frac {n}{2}$

Prove by induction $1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \ldots + \frac{1}{2^n} \ge 1 + \frac {n}{2}$ I can't explain in words how the left hand side of the equation is achieved soI shall ...
0
votes
2answers
45 views

Proofs for $g(x)=e^{-1/x^2}$ when $x\neq0$, and $g(x)=0$ when $x=0$

Sorry for the non-descriptive title - the question is a bit long. I have $g(x)$ as in the title, and we proved previously that $g'(0)=0$ using L'Hôpital's rule. Now I must show by induction that ...
1
vote
4answers
95 views

proof by induction: sum of binomial coefficients

Question: Prove that the sum of the binomial coefficients for the nth power of $(x + y)$ is $2^n$. i.e. the sum of the numbers in the $(n + 1)^{st}$ row of Pascal’s Triangle is $2^n$ i.e. prove ...
1
vote
1answer
32 views

Binomial Coefficient Recusions

Let m and j be non-negative integers. Define $S^{0}_{m} = 1$ and: $ S^{j}_{m} = \displaystyle\sum\limits_{i=1}^{m} S_{i}^{j-1}$ Show via induction: $ S_{m}^{j} = {m+j-1 \choose j} $ I can ...
2
votes
3answers
63 views

Mathematical induction proof that $8$ divides $3^{2n} - 1$

I'm struggling with this question: prove the following using simple mathematical induction. $$ 8 \mid (3^{2k} - 1) $$ What I've got so far is: $$ 3^{2k+2} - 1 = 3^{2k} \cdot 3^{2} - 1 $$ From here, ...
0
votes
2answers
43 views

Inductive proof and summation

The problem asks me to prove by induction that: $$\sum_{i=1}^n i^3 = \frac{n^2(n+1)^2}{4}$$ I've worked through it at least half a dozen times, checked my math fastidiously, can't seem to figure it ...
0
votes
2answers
31 views

Induction question help.

Let $x$ and $y$ belong to a commutative ring $R$ with prime characteristic $p$. Show that, for all positive integers $n$ $$ (( x + y )^p)^n = (x^p)^n + (y^p)^n $$ I hope you can can understand ...
3
votes
1answer
25 views

$a^{(m+n)}_{ij} \geq a^{(m)}_{ik}a^{(n)}_{kl}$ for non-negative Matrix $A$

Let $A$ be a non-negative infinite Matrix (all entries $\geq 0$). $a_{ij}^{(n)}$ denotes the $ij$-th entry of $A^n$. Does the following inequality hold: $a^{(m+n)}_{ij} \geq ...
2
votes
1answer
63 views

Help with induction proof for formula connecting Pascal's Triangle with Fibonacci Numbers

I am in the middle of writing my own math's paper on the topic of Pascal's Triangle. During the investigation I have came up with a formula for counting elements of Fibonacci Sequence using the ...
0
votes
1answer
29 views

Inductive Proof Recursive Definition

Using this recursive Definition: $$a_{n} = \left\{\begin{matrix} 4 & n=1\\ a_{n-1}+4n-5 & n \geq 2 \end{matrix}\right.$$ I somehow have to prove using induction $$a_{n} = 2n^{2} - ...
0
votes
1answer
42 views

Fibonacci Proof with Induction [duplicate]

$$f(n) = \left\{\begin{matrix} 0 & n=1\\ 1 & n=2\\ f_{n-1} + f_{n-2} & n\geqslant 2\end{matrix}\right.$$ How can I prove by induction that $$f_{n} \geq \left ( 1.5 \right )^{n-1}$$ ...
2
votes
2answers
56 views

Fibonacci Proof Using Induction

$$f(n) = \left\{\begin{matrix} 0 & n=1\\ 1 & n=2\\ f_{n-1} + f_{n-2} & n\geqslant 2\end{matrix}\right.$$ How can I prove by induction that $$f_{n} \leq \left ( \frac{1+\sqrt{5}}{2} ...
2
votes
1answer
55 views

Fibonacci proof by induction

I have fibonacci numbers defined as such: $$ f(n) = f(n-1) + f(n-2)$$with$$ f(0) = 0 $$$$f(1) = 1$$ I have to prove that $$ F(n) \geq 1.5^{n-1}, n \geq 6$$ Base Case: $$ f(6) = 8 \geq (1.5)^5 ...
0
votes
3answers
37 views

Divisibility proof by induction.

$ 169$ | $3^{3n+3}-26n-27$ ? Fulfilled for $n=0$. Induction to $n+1$: An integer $x$ exists so that $ 169x= 3^{3n+6}-26n-27-26$ $ 169x= 27*3^{3n+3}-26n-27-26$ $ 169x= 26*3^{3n+3}+3^{3n+3}-26n-27-26$ ...
0
votes
3answers
31 views

Induction summation proof

Don't want a full answer but can somebody help me in the right direction with this problem. Have to prove using induction $$\forall n \geqslant 2: \sum_{i=1}^{n} \frac{4}{5^{i}} < 1$$
2
votes
0answers
46 views

My first proof employing strong induction / complete induction (very simple number theory). Please mark/grade.

What do you think about my first proof employing strong induction? What mark/grade would you give me? Theorem Every natural number greater than 1 is a product of one or more primes. Proof First, ...
0
votes
1answer
28 views

Composition of linear maps and induction

With DonAntonio's help Composition of linear maps. I managed to find $t^4 = t^2 +4(t^2- id)$ , $t^6 = t^2 + 4(4+1) (t^2 -id)$ and $t^8 = t^2 + 4 ( 1+ 4 +4^2)(t^2 -id) $ So now I want to prove it ...
17
votes
3answers
706 views

My first induction proof (very simple number theory). Please mark/grade.

What do you think about my first induction proof? Please mark/grade. Theorem The sum of the cubes of three consecutive natural numbers is a multiple of 9. Proof First, introducing a predicate ...
1
vote
1answer
87 views

Can't find an identy for proving that $ \sum_{k=0}^{i+1} \binom {i+1} k=2^{i+1}$ [duplicate]

$$ \sum_{k=0}^{i+1} \binom {i+1} k$$ I can't find an identity for this summation :( To clarify I'm trying to prove using induction that this sum is equal to $2^{i+1}$, I have my basis and ...
0
votes
1answer
18 views

Prove that all elements in the set T is divisible by 3 using structural induction.

Let T be the set defined recursively as follows: (1) (0,3) $\in$ T (2) If (x, y) $\in$ T, then (x + 2, y - 1) $\in$ T and (x - 3, y) $\in$ T. (3) Every element of T can be obtained from (1) by ...
1
vote
0answers
50 views

Proof by induction on contraction mapping?

Let $k:[0,1] \times [0,1] \to \mathbb{R}$ be continous, and $x(t) = \int_0^t k(t,s)x(s)ds$ for $0 \leq t \leq 1$. Not let $Tx(t) = \int_0^t k(t,s)x(s)ds$ and suppose $sup_{0 \leq t, s \leq 1}|k(t,s)|= ...
0
votes
3answers
62 views

Proving by mathematical induction

Let $d \in N $ be an odd integer. Prove by induction that: $\forall k \in N$ , $d^k$ = 1 (mod 2). How do I begin this question? I have a hard time understanding what to do for the inductive step. ...
0
votes
9answers
402 views

How to prove for each positive integer $n$, the sum of the first $n$ odd positive integers is $n^2$?

I'm new to induction so please bear with me. How can I prove using induction that, for each positive integer $n$, the sum of the first $n$ odd positive integers is $n^2$? I think $9$ can be an ...
0
votes
0answers
42 views

Prove $F_{n+2} \ge x^n$ by induction where $x = (1 + \sqrt{5})/2$

Base Case: $n = 1$: $F_3 \ge x^1$ translates to $3 \ge 1.6$, so the base case holds. Induction Hypothesis: Assume the statement is true for all $n$ such that 40 \le n \le k$. We will prove this ...
0
votes
0answers
40 views

How to use two types different forms of induction to prove stamp problem?

For this problem I have to prove using two different types of induction to show that using only 3 cent stamps and 5 cent stamps, any postage amount 8 cents or greater can be formed. Using the two ...
0
votes
0answers
41 views

Proving this property of a tournament graph by induction?

I am working on practicing proofs by induction. Can you please take a look at the proof below and tell me if I proved it correctly? I am particularly worried about the inductive step. Definition ...
0
votes
1answer
35 views

How can I prove prime factorization theorem by induction?

The prime factorization including both existence and uniqueness. I have totally no idea about this problem except the basecase. In this problem we only consider number greater or equal to 2. So the ...
1
vote
4answers
99 views

prove that a power of odd number is always odd by induction.

The problem has confused me for like half hour. An integer is odd if it can be written as d = 2m+1. Use induction to prove that the ${d^n}$ = 1 (mod 2) by induction, the basecase is pretty simple , ...
0
votes
1answer
68 views

Cayley's formula for the number of trees(Recursion)

I'm trying to understand the proof by recurcion and induction for the Cayley's formula for the number of trees.While I'm trying to understand it there are some things that I don't get at all. -It ...
1
vote
5answers
126 views

How to prove that $n^5 - n$ is a multiple of $5$? [duplicate]

Hello I'm new to induction so please bare with me. For this problem I have to use induction to prove: For every integer $n\geq 1$, the number $n^5 − n$ is a multiple of $5$. Can someone please help me ...
1
vote
1answer
42 views

How would I solve this mathematical induction proof? I am stuck after the first part of the induction.

$$1 + 5 + 5^2 + \ldots + 5^n = \frac{5^{n+1}-1}{4}$$ Basis case $n= 0$: $1^0 = 1 \;\;\;\;\;\;\;\;\;\;\;\; \frac{5^{1+1}-1}{4}=1$ Assume true for $n=k$: $$1 + 5 + 5^2 + \ldots + 5^k = ...
0
votes
3answers
46 views

proving golden ration with induction

If $\displaystyle a=\frac{1+\sqrt{5}}{2}$ and $\displaystyle b=\frac{1-\sqrt{5}}{2}$, prove that $\displaystyle f_n=\frac{a^n-b^n}{\sqrt{5}}$ for all $n\in\mathbb{P}$ Would we start with a base case ...
1
vote
2answers
46 views

Proving an inequality using induction

Use induction to prove the following: $\frac{1}{1}+\frac{1}{2}+\frac{1}{3}+\ldots+\frac{1}{2^n}\geq1+\frac{n}{2}$ What would the base case be? Would it still be $n=0$ so ...
1
vote
4answers
61 views

Proof by induction

Prove that the inequality $n^2\geq n$ holds for every integer. With induction, I believe we would start with the base case, that is $n=0$ $n=0$ $0^2 \geq 0$, which is true. Then would I start with ...
3
votes
2answers
58 views

Help finishing proof via induction for a summation

So I have to prove the following equation using induction for n >= 2: $$ \sum\limits_{i=1}^n 4/5^i < 1 $$ However the question asks me to prove something stronger such as this: $$ ...