# Tagged Questions

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

37 views

### Show the sequence [fn]= 1+(1/1!)+(1/2!)…+(1/n!) is increasing and bounded above by 3. [duplicate]

This is part of a question. In the end we are trying to show the sequence up above converges to e. I need to use math induction.
17 views

### Non inductive proof for square of odd integers [duplicate]

Can we argue that the square of every odd integer is of the form $8k+1$ using non inductive proof?
47 views

88 views

### Show that $(a_1\cdot a_2\cdot …\cdot a_n)^\frac 1n \leq (a_1+…+a_n)/n$ [duplicate]

Sorry if it is sort of hard to read so here it is in words. Show that the nth root of the product of n terms is less than or equal to the sum of n terms divided by n. Our instructions are to use a ...
44 views

44 views

### How to show using proof by induction: $\sqrt[n]{n!} \leqslant \frac{n+1}{2}, n \in \mathbb{Z}^+$

I'm having quite a few problems with the following proof by induction question: $$\sqrt[n]{n!} \leqslant \frac{n+1}{2}, n \in \mathbb{Z}^+$$ I manage to do the easy parts of the base step ($n=1$) ...
184 views

### $n\times n$ chessboard game with coins

The rows and the columns of an $n\times n$ chessboard are numbered $1$ to $n$, and a coin is placed on each field. The following game is played: A coin showing tails is selected. If it is in row $x$ ...
76 views

### Prove by strong induction that $3^n$ divides $a_n$ for all integers $n \ge 1$

Let $a_1 = 3, a_2 = 18$, and $a_n = 6a_{n-1} − 9a_{n-2}$ for each integer $n \ge 3$. Prove by strong induction that $3^n$ divides $a_n$ for all integers $n \ge 1$ I've done the base step and ih ...
72 views

68 views

### Proof by Induction

I am attempting to prove by induction that the algorithm calculates the cube of a number, I can't for the life of my grasp it. I was wondering if someone could help me please. The question is: A ...
42 views

### Help With an (structural) Induction proof on ordered pair

This is a Structural Induction proof. I don't want the solution, just some help in the right direction. I know normally in structural induction proofs, you use your base case, with the recursive step ...
18 views

### Induction with associative binary operation

Let * be an associative binary operation on a set 'A' with identity element e. Let 'B' be a subset of 'A' that is closed under *. Let b1, b2, b3, ... bn ∈ B. Prove that b1 * b2 * b3... bn ∈ B. ...
48 views

### Proofs and definitions.

I am a first-year university student and even with help from tutors I have a difficult time understanding proofs. In particular I notices that when using proofs (be it by induction or contradiction) ...
48 views

### “Right” way to get from $P(n)$ to $P(n+1)$ in an inductive step?

I'm reading a Math lecture note on mathematical induction, and in it, the author condemns a way of concluding that $\ P(n) \implies P(n+1)\$, which is done by assuming $\ P(n+1)$, making a few ...
26 views

### Induction proof of a Recurrence Relation?

Consider the following recurrence equation obtained from a recursive algorithm: Using Induction on n, prove that: So I got my way thru step1 and step2: the base case and hypothesis step but I'...
28 views

### prove by induction: $x_n=a^nx_0+b(1+a+\cdots+a^{n-1})$ given $f(x)=ax+b$ with initial value $x_0$

prove by induction: $x_n=a^nx_0+b(1+a+\cdots+a^{n-1})$ given $f(x)=ax+b$ with initial value $x_0$ I'm fine with base case and hypothesis, but having some problems showing that it is true for $P(n+1)$ ...
51 views

### Proof by Induction: Number of bit strings of length $n$ starting with a 1 or ending with a 0 [duplicate]

We showed that the number of bitstrings of length $n$ that begin with a 1 or end with a 0 (or both) is $3 \cdot 2^{n−2}$. Sketch a proof by induction for this. Would we prove this by manipulation? I'...
32 views

### Induction proof (bitstring length)

Theorem : The number of bitstrings with the length $x$ that begin with $1$ and/or end with $0$ is $3 \times 2^{x-2}$. I know there are easier ways to prove this but I must figure out how to do it ...
48 views

### Induction Proof: If $B \subseteq A$, then $|B| \leq |A|$.

Prove by induction that if $A$ is a finite set and $B$ is a subset of $A$, then $|B|≤ |A|$. I can prove the base case with $n=0$ easily, but am stuck as to how to proceed from there.
35 views

37 views

### Induction: finding a formula equal to the one given [closed]

so i needed help Determining the formual for $\sum_{k=1}^n (2k-1)$ I understand now. Thankyou every one for your time and help!
### Give a formal proof by induction that $f^k(m, n) = (m − kn, n)$ for all $k\in\Bbb Z^+$.
i understand in general how an induction proof works, however I'm having difficulties with the following question: Let $f :\Bbb Z^2 \to\Bbb Z^2$ be given by $f(m, n) = (m − n, n)$. The composite ...